N-Queens

Hard

#0051Time: O(N! * N)Space: O(N^2)16 companies

Patterns

Backtracking

Data structures

Array

Companies

Adobe Amazon Apple Bloomberg

Prompt

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

Constraints:

1 <= n <= 9

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a standard backtracking algorithm to explore all possible placements of queens, one row at a time. For each potential queen placement, it validates the move by checking all previously placed queens to ensure there are no attacks. This validation step involves scanning the columns and diagonals.

Algorithm

Create a recursive function backtrack(row, board).
Base Case: If row equals n, a solution has been found. Convert the board to the required list of strings format and add it to the results.
Recursive Step: For the current row, iterate through each column col from 0 to n-1.
For each cell (row, col), check if it's a safe position to place a queen using a helper function isSafe().
The isSafe() function checks upwards from (row, col) for any other queens in the same column or diagonals. This takes O(N) time.
If the position is safe, place a queen at board[row][col] = 'Q'.
Make a recursive call: backtrack(row + 1, board).
After the recursive call returns, backtrack by removing the queen from board[row][col] to explore other possibilities.

Walkthrough

The core idea is a recursive function, let's call it backtrack(row, board). The function tries to place a queen in the given row. It iterates through all columns col from 0 to n-1 for the current row. For each (row, col), it calls a helper function isSafe(row, col, board) to check if placing a queen there is valid. The isSafe function checks three conditions for all previously placed queens (in rows 0 to row-1):

No queen in the same column.
No queen on the upper-left diagonal.
No queen on the upper-right diagonal.

This check takes O(row) time, which is O(n) in the worst case. If isSafe returns true, we place the queen (board[row][col] = 'Q'), and recursively call backtrack(row + 1, board). After the recursive call returns, we must backtrack by removing the queen (board[row][col] = '.') to explore other possibilities in the current row. The base case for the recursion is when row == n, which means we have successfully placed n queens. At this point, we format the current board configuration and add it to our list of solutions.

1class Solution {2    public List<List<String>> solveNQueens(int n) {3        List<List<String>> result = new ArrayList<>();4        char[][] board = new char[n][n];5        for (int i = 0; i < n; i++) {6            for (int j = 0; j < n; j++) {7                board[i][j] = '.';8            }9        }10        backtrack(0, n, board, result);11        return result;12    }13 14    private boolean isSafe(int row, int col, char[][] board, int n) {15        // Check column upwards16        for (int i = 0; i < row; i++) {17            if (board[i][col] == 'Q') {18                return false;19            }20        }21        // Check upper-left diagonal22        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {23            if (board[i][j] == 'Q') {24                return false;25            }26        }27        // Check upper-right diagonal28        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {29            if (board[i][j] == 'Q') {30                return false;31            }32        }33        return true;34    }35 36    private void backtrack(int row, int n, char[][] board, List<List<String>> result) {37        if (row == n) {38            result.add(constructSolution(board));39            return;40        }41        for (int col = 0; col < n; col++) {42            if (isSafe(row, col, board, n)) {43                board[row][col] = 'Q';44                backtrack(row + 1, n, board, result);45                board[row][col] = '.'; // Backtrack46            }47        }48    }49 50    private List<String> constructSolution(char[][] board) {51        List<String> solution = new ArrayList<>();52        for (int i = 0; i < board.length; i++) {53            solution.add(new String(board[i]));54        }55        return solution;56    }57}

Complexity

Time

O(N! * N)

Space

O(N^2)

Trade-offs

Pros

Conceptually straightforward implementation of backtracking.
Does not require extra space for tracking attacked squares, relying only on the board itself.

Cons

Inefficient due to the O(N) safety check performed at every step of the recursion.
For larger N (though outside the problem constraints), this approach would be significantly slower than optimized versions.

This approach improves upon the basic backtracking solution by optimizing the safety check. Instead of scanning the board each time, it uses auxiliary data structures (like boolean arrays) to keep track of which columns and diagonals are already under attack. This allows for an O(1) time complexity for the safety check at each step.

Algorithm

Initialize boolean arrays: cols[n], diag1[2n-1], and diag2[2n-1] to track attacked columns and diagonals.
Create a recursive function backtrack(row).
Base Case: If row equals n, a solution is found. Add the current board configuration to the results.
Recursive Step: For the current row, iterate through each column col from 0 to n-1.
Calculate diagonal indices: d1 = row - col + n - 1 and d2 = row + col.
Check in O(1) time if the position is safe: !cols[col] && !diag1[d1] && !diag2[d2].
If safe, place the queen, mark the corresponding column and diagonals as occupied in the boolean arrays, and make a recursive call: backtrack(row + 1).
After the call returns, backtrack by removing the queen and un-marking the column and diagonals in the boolean arrays.

Walkthrough

This optimized approach maintains the same backtracking structure but drastically speeds up the validation process. We use three boolean arrays to keep track of attacked squares:

cols[n]: cols[c] is true if column c is occupied.
diag1[2n-1]: For anti-diagonals. All cells (r, c) on the same anti-diagonal have a constant r - c. We map this value (from -(n-1) to n-1) to an index r - c + n - 1.
diag2[2n-1]: For main-diagonals. All cells (r, c) on the same main-diagonal have a constant r + c. This value (from 0 to 2n-2) can be used directly as an index.

With these arrays, checking if a cell (row, col) is safe becomes an O(1) lookup. When we place a queen, we set the corresponding indices in the three arrays to true. When we backtrack, we reset them to false. This eliminates the O(N) scan required in the previous approach.

For even better performance, the boolean arrays can be replaced with integer bitmasks. Each bit in the integer can represent a column or a diagonal, and checks/updates can be done using fast bitwise operations. This doesn't change the asymptotic complexity but can be faster in practice.

1class Solution {2    private List<List<String>> result;3    private char[][] board;4    private int n;5    private boolean[] cols;6    private boolean[] diag1; // For diagonals where row - col is constant7    private boolean[] diag2; // For diagonals where row + col is constant8 9    public List<List<String>> solveNQueens(int n) {10        this.n = n;11        this.result = new ArrayList<>();12        this.board = new char[n][n];13        for (int i = 0; i < n; i++) {14            for (int j = 0; j < n; j++) {15                board[i][j] = '.';16            }17        }18        19        this.cols = new boolean[n];20        this.diag1 = new boolean[2 * n - 1];21        this.diag2 = new boolean[2 * n - 1];22        23        backtrack(0);24        return result;25    }26 27    private void backtrack(int row) {28        if (row == n) {29            result.add(constructSolution());30            return;31        }32 33        for (int col = 0; col < n; col++) {34            int d1Index = row - col + n - 1;35            int d2Index = row + col;36 37            if (!cols[col] && !diag1[d1Index] && !diag2[d2Index]) {38                // Place queen39                board[row][col] = 'Q';40                cols[col] = true;41                diag1[d1Index] = true;42                diag2[d2Index] = true;43 44                // Recur for next row45                backtrack(row + 1);46 47                // Backtrack48                board[row][col] = '.';49                cols[col] = false;50                diag1[d1Index] = false;51                diag2[d2Index] = false;52            }53        }54    }55 56    private List<String> constructSolution() {57        List<String> solution = new ArrayList<>();58        for (int i = 0; i < n; i++) {59            solution.add(new String(board[i]));60        }61        return solution;62    }63}

Complexity

Time

O(N!)

Space

O(N^2)

Trade-offs

Pros

Highly efficient due to the O(1) safety check.
This is the standard and most common solution for the N-Queens problem.

Cons

Requires extra O(N) space for the tracking arrays.
The logic for diagonal indexing can be slightly more complex to grasp initially.

Solutions

Solution

1public class Solution { private int n ; private int [] col ; private int [] dg ; private int [] udg ; private IList < IList < string >> ans = new List < IList < string >>(); private IList < string > t = new List < string >(); public IList < IList < string >> SolveNQueens ( int n ) { this . n = n ; col = new int [ n ]; dg = new int [ n << 1 ]; udg = new int [ n << 1 ]; dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i == n ) { ans . Add ( new List < string >( t )); return ; } for ( int j = 0 ; j < n ; ++ j ) { if ( col [ j ] + dg [ i + j ] + udg [ n - i + j ] == 0 ) { char [] row = new char [ n ]; Array . Fill ( row , '.' ); row [ j ] = 'Q' ; t . Add ( new string ( row )); col [ j ] = dg [ i + j ] = udg [ n - i + j ] = 1 ; dfs ( i + 1 ); col [ j ] = dg [ i + j ] = udg [ n - i + j ] = 0 ; t . RemoveAt ( t . Count - 1 ); } } } }

1class Solution {2private3  List<List<String>> ans = new ArrayList<>();4private5  int[] col;6private7  int[] dg;8private9  int[] udg;10private11  String[][] g;12private13  int n;14public15  List<List<String>> solveNQueens(int n) {16    this.n = n;17    col = new int[n];18    dg = new int[n << 1];19    udg = new int[n << 1];20    g = new String[n][n];21    for (int i = 0; i < n; ++i) {22      Arrays.fill(g[i], ".");23    }24    dfs(0);25    return ans;26  }27private28  void dfs(int i) {29    if (i == n) {30      List<String> t = new ArrayList<>();31      for (int j = 0; j < n; ++j) {32        t.add(String.join("", g[j]));33      }34      ans.add(t);35      return;36    }37    for (int j = 0; j < n; ++j) {38      if (col[j] + dg[i + j] + udg[n - i + j] == 0) {39        g[i][j] = "Q";40        col[j] = dg[i + j] = udg[n - i + j] = 1;41        dfs(i + 1);42        col[j] = dg[i + j] = udg[n - i + j] = 0;43        g[i][j] = ".";44      }45    }46  }47}

1class Solution {2public:3  vector<vector<string>> solveNQueens(int n) {4    vector<int> col(n);5    vector<int> dg(n << 1);6    vector<int> udg(n << 1);7    vector<vector<string>> ans;8    vector<string> t(n, string(n, '.'));9    function<void(int)> dfs = [&](int i) -> void {10      if (i == n) {11        ans.push_back(t);12        return;13      }14      for (int j = 0; j < n; ++j) {15        if (col[j] + dg[i + j] + udg[n - i + j] == 0) {16          t[i][j] = 'Q';17          col[j] = dg[i + j] = udg[n - i + j] = 1;18          dfs(i + 1);19          col[j] = dg[i + j] = udg[n - i + j] = 0;20          t[i][j] = '.';21        }22      }23    };24    dfs(0);25    return ans;26  }27};

1class Solution:2    def solveNQueens(self, n: int) -> List[List[str]]: def dfs(i: int): if i == n: ans . append(["" . join(row) for row in g]) return for j in range(n): if col[j] + dg[i + j] + udg[n - i + j] == 0: g[i][j] = "Q" col[j] = dg[i + j] = udg[n - i + j] = 1 dfs(i + 1) col[j] = dg[i + j] = udg[n - i + j] = 0 g[i][j] = "." ans = [] g = [["."] * n for _ in range(n)] col = [0] * n dg = [0] * (n << 1) udg = [0] * (n << 1) dfs(0) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem