DSA Tracker

Visualize

N-Queens

Row-by-row backtracking with column and diagonal sets

time O(n!)space O(n)

Two queens in one row always attack each other, so every valid board has exactly one queen per row. That turns a board search into a much smaller one: decide row 0, then row 1, and so on, and the only thing to check for a candidate column is whether an earlier queen sits in the same column or on one of its two diagonals. Cells on a diagonal all share the same row - col, and cells on an anti-diagonal share the same row + col, so three sets answer that in O(1). When a row has no safe column, the choice in the row above was wrong: undo it (backtrack) and try the next column there. Reaching row n means a full board, which is recorded, and the search keeps going until every branch is explored.

Details

Animated on: n = 4. Place 4 queens on a 4x4 board so no two share a row, column or diagonal; return every distinct board. Answer: 2 solutions, cols [[1, 3, 0, 2], [2, 0, 3, 1]].

Problem:N-QueensHard

Pattern:Backtracking with Constraints

Row-by-row backtracking with column and diagonal sets

step 1 / 15

.
[0]
.
[1]
.
[2]
.
[3]

n = 4. Every row must hold exactly one queen, so the board collapses to one number per row: cols[r] is the column of the queen in row r. Placing row by row means rows can never clash, leaving only columns and the two diagonals to check. Start at row 0 with nothing placed.

  • row=0· arr[0] = .
Pseudocode
1FUNCTION solveNQueens(n)
2  out <- EMPTY LIST
3  cols <- ARRAY OF n EMPTY SLOTS
4  FUNCTION place(row)
5    IF row = n
6      APPEND BOARD(cols) TO out
7      RETURN
8    FOR c <- 0 TO n - 1
9      IF c IN usedCols OR row - c IN diag1 OR row + c IN diag2
10        CONTINUE
11      cols[row] <- c
12      ADD c TO usedCols, row - c TO diag1, row + c TO diag2
13      place(row + 1)
14      REMOVE c FROM usedCols, row - c FROM diag1, row + c FROM diag2
15  place(0)
16  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. n = 4. Every row must hold exactly one queen, so the board collapses to one number per row: cols[r] is the column of the queen in row r. Placing row by row means rows can never clash, leaving only columns and the two diagonals to check. Start at row 0 with nothing placed.
  2. Row 0: col 0 is the first column no earlier queen attacks: column 0 is free, diagonal 0 is free and anti-diagonal 0 is free. Place it, mark all three, and go down to row 1. Queens now at (0, 0).
  3. Row 1: col 0 (column 0 is taken by row 0); col 1 (it shares a diagonal with (0, 0)) — so col 2 is the first column no earlier queen attacks: column 2 is free, diagonal -1 is free and anti-diagonal 3 is free. Place it, mark all three, and go down to row 2. Queens now at (0, 0), (1, 2).
  4. Row 2 is exhausted: col 0 (column 0 is taken by row 0); col 1 (it shares an anti-diagonal with (1, 2)); col 2 (it shares a diagonal with (0, 0)); col 3 (it shares a diagonal with (1, 2)). So the queen in row 1 is what has to move: its placement is undone (the sets are cleared again) and its loop tries the next column. Queens still standing: (0, 0), (1, 2).
  5. Row 1: col 0 (column 0 is taken by row 0); col 1 (it shares a diagonal with (0, 0)) — so col 3 is the first column no earlier queen attacks: column 3 is free, diagonal -2 is free and anti-diagonal 4 is free. Place it, mark all three, and go down to row 2. Queens now at (0, 0), (1, 3).
  6. Row 2: col 0 (column 0 is taken by row 0) — so col 1 is the first column no earlier queen attacks: column 1 is free, diagonal 1 is free and anti-diagonal 3 is free. Place it, mark all three, and go down to row 3. Queens now at (0, 0), (1, 3), (2, 1).
  7. Row 3 is exhausted: col 0 (column 0 is taken by row 0); col 1 (it shares an anti-diagonal with (1, 3)); col 2 (it shares a diagonal with (2, 1)); col 3 (it shares a diagonal with (0, 0)). So the queen in row 2 is what has to move: its placement is undone (the sets are cleared again) and its loop tries the next column. Queens still standing: (0, 0), (1, 3), (2, 1).
  8. Row 2 is exhausted: col 1 could be placed but every row below then ran out of safe columns, and col 0 (column 0 is taken by row 0); col 2 (it shares a diagonal with (0, 0)); col 3 (column 3 is taken by row 1). So the queen in row 1 is what has to move: its placement is undone (the sets are cleared again) and its loop tries the next column. Queens still standing: (0, 0), (1, 3).
  9. Row 1 is exhausted: cols 2, 3 could be placed but every row below then ran out of safe columns, and col 0 (column 0 is taken by row 0); col 1 (it shares a diagonal with (0, 0)). So the queen in row 0 is what has to move: its placement is undone (the sets are cleared again) and its loop tries the next column. Queens still standing: (0, 0).
  10. Row 0: col 1 is the first column no earlier queen attacks: column 1 is free, diagonal -1 is free and anti-diagonal 1 is free. Place it, mark all three, and go down to row 1. Queens now at (0, 1).
  11. Row 1: col 0 (it shares an anti-diagonal with (0, 1)); col 1 (column 1 is taken by row 0); col 2 (it shares a diagonal with (0, 1)) — so col 3 is the first column no earlier queen attacks: column 3 is free, diagonal -2 is free and anti-diagonal 4 is free. Place it, mark all three, and go down to row 2. Queens now at (0, 1), (1, 3).
  12. Row 2: col 0 is the first column no earlier queen attacks: column 0 is free, diagonal 2 is free and anti-diagonal 2 is free. Place it, mark all three, and go down to row 3. Queens now at (0, 1), (1, 3), (2, 0).
  13. Row 3: col 0 (column 0 is taken by row 2); col 1 (column 1 is taken by row 0) — so col 2 is the first column no earlier queen attacks: column 2 is free, diagonal 1 is free and anti-diagonal 5 is free. Place it, mark all three, and go down to row 4. Queens now at (0, 1), (1, 3), (2, 0), (3, 2).
  14. row = 4 means every row holds a queen: [1, 3, 0, 2] is solution #1, drawn as [".Q..", "...Q", "Q...", "..Q."]. The search does not stop here — the loop in row 3 continues, and every remaining branch is explored the same way.
  15. Search complete. After solution #1 the same loop kept going, and by symmetry the board mirrored left-to-right is the only other arrangement: 2 solutions in total for n = 4, [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]. Marking a column and its two diagonals in sets makes each check O(1), so the cost is the size of the search tree, not the board scan.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve N-Queens in the editorAll Backtracking problemsBack to roadmap