loading

51. N-Queens — Step-by-Step Visualization

hardLeetCode #51ArrayBacktracking

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.."]]` **Example 2:** Input: `n = 1` Output: `[["Q"]]`

Algorithm Pattern

Backtracking / State Sets

Key Idea

We place queens row-by-row. To efficiently check if a position is valid, we track three conflicts: columns, positive diagonals (r + c), and negative diagonals (r - c). For an $n imes n$ board, if we find a valid configuration for all $n$ rows, we have a solution.

Step-by-Step Approach

  1. Initialize an empty board and three sets (`cols`, `posDiag`, `negDiag`) to track conflicts.
  2. In the backtrack function for row `r`:
  3. 1. If `r == n`, a solution is found! Add the current board configuration to our results.
  4. 2. For each column `c` in `0...n-1`:
  5. - Check if `c` is in `cols`, `r+c` in `posDiag`, or `r-c` in `negDiag`.
  6. - If no conflict: Place queen at `(r, c)`, add to sets, and recurse on `r + 1`.
  7. - After recursion: 'Backtrack' by removing the queen and the conflicts from the sets.

Common Gotchas

  • Diagonals are tricky: there are $2n-1$ possible diagonals in each direction.
  • The value of `r - c` can be negative, which is fine for a Set, but if using an array index, you'd need an offset.

Related Problems

← All problems