N queens Problem

Dec 18, 2024 • 5 mins read
Hero Image

DT

Dhaval Trivedi

Co-founder, Airtribe

Problem Overview

The N-Queens problem is a classic computer science and combinatorial problem, typically presented as follows: given an integer n, you need to place n queens on an n x n chessboard such that no two queens threaten each other. This means no two queens should be placed in the same row, column, or diagonal. The goal is to return all distinct solutions to the N-Queens puzzle.

Understanding the Problem

Imagine a standard chessboard; the problem extends to an n x n board where you must place n queens. A queen can attack in a straight line: vertically, horizontally, and diagonally. Therefore, each solution must ensure queens are placed such that none can attack another.

For example, with n = 4, one valid solution looks like this:

. Q . .
. . . Q
Q . . .
. . Q .

The board above represents a solution where each Q denotes a queen's position.

Key DSA Concepts and Theory

Recursion and Backtracking

  1. Recursion is a method of solving problems where a function calls itself as a sub-routine. Problems solved via recursion can often be framed in terms of smaller identical problems.

  2. Backtracking is a refinement over the brute force approach. It systematically searches for a solution to a problem among all available options. The idea is to build the solution piece by piece and remove those solutions that do not satisfy the constraints of the problem.

Combining Recursion and Backtracking for N-Queens

  • We place queens on the board one by one using recursion. Starting from the first row, we try to place a queen in every cell and recur for the remaining n-1 queens.
  • Whenever a cell is deemed unsafe due to another queen's presence, backtrack and try another cell.

Solution Approach

The solution involves two primary steps:

  1. Recursive Function:

    • Utilize a recursive function to attempt to place queens.
    • For each row, try every column to see if it is safe to place a queen.
    • Use additional data structures to track columns and diagonals that threaten the queens.

  2. Backtracking:

    • If placing a queen in a column is valid, proceed to the next row with this new state.
    • If not, remove the queen and continue checking in the next column.

C++ Code Example

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> solutions;
        vector<int> queens(n, -1);
        vector<bool> columns(n, false), diag1(2 * n - 1, false), diag2(2 * n - 1, false);
        backtrack(solutions, queens, n, 0, columns, diag1, diag2);
        return solutions;
    }
    
private:
    void backtrack(vector<vector<string>>& solutions, vector<int>& queens, int n, int row,
                   vector<bool>& columns, vector<bool>& diag1, vector<bool>& diag2) {
        if (row == n) {
            vector<string> board = generateBoard(queens, n);
            solutions.push_back(board);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (columns[i] || diag1[row - i + n - 1] || diag2[row + i]) {
                continue;
            }
            queens[row] = i;
            columns[i] = diag1[row - i + n - 1] = diag2[row + i] = true;
            backtrack(solutions, queens, n, row + 1, columns, diag1, diag2);
            columns[i] = diag1[row - i + n - 1] = diag2[row + i] = false;
        }
    }
    
    vector<string> generateBoard(vector<int>& queens, int n) {
        vector<string> board;
        for (int i = 0; i < n; ++i) {
            string row(n, '.');
            row[queens[i]] = 'Q';
            board.push_back(row);
        }
        return board;
    }
};

Java Code Example

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        boolean[] columns = new boolean[n];
        boolean[] diag1 = new boolean[2 * n - 1];
        boolean[] diag2 = new boolean[2 * n - 1];
        backtrack(solutions, queens, n, 0, columns, diag1, diag2);
        return solutions;
    }
    
    private void backtrack(List<List<String>> solutions, int[] queens, int n, int row,
                           boolean[] columns, boolean[] diag1, boolean[] diag2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (columns[i] || diag1[row - i + n - 1] || diag2[row + i]) {
                continue;
            }
            queens[row] = i;
            columns[i] = diag1[row - i + n - 1] = diag2[row + i] = true;
            backtrack(solutions, queens, n, row + 1, columns, diag1, diag2);
            columns[i] = diag1[row - i + n - 1] = diag2[row + i] = false;
        }
    }
    
    private List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}

Time and Space Complexity Analysis

  • Time Complexity: The complexity is O(N!), which corresponds to the number of permutations of N queens. As each queen has N potential positions to be placed, the number of valid placements decreases rapidly due to constraints.

  • Space Complexity: O(N^2), considering the storage for the board configuration and auxiliary arrays for columns and diagonals.

Common Mistakes to Avoid

  • Overlapping Diagonals: A common pitfall is mishandling the indices for diagonals (especially the formula: row - col + n - 1 and row + col).
  • Incorrect Base Cases: Ensure that the recursion base case is correctly identifying a valid solution (row == n).

Similar Problems on LeetCode

Additional Resources and References

The N-Queens problem is an excellent introduction to recursion and backtracking, teaching key aspects of problem-solving, optimization, and constraint satisfaction.