Skip to content
Tutorials Center
My learning

Topics

Lesson 65 of 225 ยท Recursion and Backtracking

N-Queens

Solve the N-Queens problem in Python with backtracking: constraint checking with sets, diagonal formulas, solution counts for n=1 to 8, board printing and bitmask speed-up.

On a chess board a queen attacks every square in her row, her column and both diagonals. The N-Queens problem asks: can you place n queens on an n x n board so that no two attack each other? For n = 8 (a normal chess board) the answer is yes, in exactly 92 different ways. For n = 2 and n = 3 there is no solution at all.

N-Queens is the classic showcase for backtracking. It has a tiny rule set, a huge search space, and a beautiful speed-up from pruning. In this lesson you will count the brute-force possibilities, build the pruned solution with constant-time constraint checks, count solutions for n = 1 to 8, print boards, and see a bitmask version.

The search space

A board has n^2 squares. Choosing n of them for the queens gives C(n^2, n) placements: for n = 8 that is C(64, 8) = 4,426,165,368, over four billion. We can immediately do better with one observation: there must be exactly one queen in every row (two in the same row would attack each other, and we need n queens in n rows). So we place one queen per row, row by row, and only need to choose the column for each row. That gives n^n possibilities (8^8 = 16,777,216), and requiring distinct columns makes it n! = 40,320 permutations. Backtracking with early checks visits far fewer still.

TEXT
Row 0:  queen in column c0
Row 1:  queen in column c1 (not c0, not diagonal to c0)
Row 2:  queen in column c2 (not in a used column, not on a used diagonal)
...

Checking attacks in O(1)

Place queens row by row, and keep three sets: used columns, used "down-right" diagonals and used "down-left" diagonals. A square (row, col) lies on:

  • column col;
  • the diagonal where row - col is constant (call it the main diagonal);
  • the anti-diagonal where row + col is constant.
TEXT
Values of row + col (anti-diagonals)      Values of row - col (diagonals)
   col: 0 1 2 3                              col:  0  1  2  3
row 0:  0 1 2 3                           row 0:   0 -1 -2 -3
row 1:  1 2 3 4                           row 1:   1  0 -1 -2
row 2:  2 3 4 5                           row 2:   2  1  0 -1
row 3:  3 4 5 6                           row 3:   3  2  1  0

Squares on the same diagonal share the same number in the table. So "is this square attacked?" becomes three set lookups: col in cols, row - col in diag, row + col in anti.

Python Which squares does a queen attack?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The backtracking solution

For each row, try every column. If the square is safe, place the queen (add to the three sets), recurse on the next row, and remove the queen (undo). When the row index reaches n, all queens are placed: count or record the solution.

Python Count the N-Queens solutions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The famous sequence appears: 1, 0, 0, 2, 10, 4, 40, 92. There are no solutions for 2 and 3, one for n = 1, and 92 for the standard board. (Many of them are rotations or mirror images: only 12 of the 92 solutions are truly different once you ignore symmetry.)

Seeing the solutions

To print a board we need the actual placements. We keep a list queens where queens[row] is the column of the queen in that row.

Python Print all solutions of 4-Queens

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two solutions for n = 4 are mirror images of each other:

TEXT
.Q..        ..Q.
...Q        Q...
Q...        ...Q
..Q.        .Q..

Tracing the search for n = 4

Backtracking tries columns left to right. Here is how it finds the first solution (X marks a dead end where no column is safe):

TEXT
row 0: try col 0 -> place Q(0,0)
  row 1: col 0 same column, col 1 diagonal -> col 2 ok -> Q(1,2)
    row 2: col 0 same column, col 1 anti-diagonal of (1,2), col 2 same column,
           col 3 diagonal of (1,2)                       -> X  (dead end)
  row 1: try col 3 -> Q(1,3)
    row 2: col 0 column, col 1 ok -> Q(2,1)
      row 3: col 0 column, col 1 column, col 2 diagonal of (2,1), col 3 column -> X
    row 2: col 2 diagonal of (1,3), col 3 column -> X
  row 1 exhausted -> backtrack to row 0
row 0: try col 1 -> Q(0,1)
  row 1: col 3 -> Q(1,3)
    row 2: col 0 -> Q(2,0)
      row 3: col 2 -> Q(3,2)   <- all four placed: solution [1, 3, 0, 2]

Each X is a branch cut by the constraints. Without pruning, you would generate full boards and check them afterwards.

How much does pruning save?

Counting the nodes (calls) visited by the backtracking search shows the effect. We compare it with the number of arrangements a naive "one queen per row, any column" search would produce at the leaves:

Python Nodes visited versus brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For n = 8, backtracking visits 2,057 calls versus 16,777,216 complete one-queen-per-row boards that brute force would examine. Pruning removes the vast majority of the tree.

Complexity

  • Time: at most O(n!) because each row picks a column not used yet, but pruning by diagonals reduces it a lot in practice. There is no polynomial-time formula for counting all solutions: the search is still exponential.
  • Space: O(n) for the three sets, the queens list and the recursion depth (the solutions list is extra output).
  • Constraint check: O(1) with sets, versus O(n) per placement if you loop over earlier queens to compare diagonals.

A faster version: bitmasks

Python integers can hold the three sets as bits. A bit set in cols means that column is taken; diag and anti shift by one every row, which keeps their bits aligned with the columns of the next row. The available squares in a row are ~(cols | diag | anti) & full, and the lowest set bit is picked with x & -x. This removes the Python set overhead.

Python N-Queens counting with bitmasks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

It prints the same numbers and extends to 352 solutions for n = 9 and 724 for n = 10. For bit tricks in general see Bit Manipulation.

Other ideas worth knowing

  • Symmetry: every solution has up to 8 equivalents (4 rotations x 2 mirrors). Solving only half of the first row and doubling halves the work.
  • Heuristics: try the columns in the middle first, or choose the most constrained row next. These help for finding one solution on huge boards.
  • Existence for every n >= 4: a constructive formula places queens without any search, so the search is only needed to count or list all solutions.
  • The same template solves Sudoku and other constraint puzzles: pick a cell, try values consistent with the rules, recurse, and undo.

Common mistakes

  • Using the same formula for both diagonals. One diagonal is constant row - col, the other constant row + col.
  • Not undoing all three sets (or undoing in a way that removes something placed by an earlier row).
  • Storing the same queens list instead of a copy in the results.
  • Checking each placement against every earlier queen, which costs O(n) instead of O(1).
  • Placing several queens in one row by looping over all squares instead of one row per level, which brings back a gigantic search space.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why can the search place exactly one queen per row?

    Two queens in a row would attack, so each of the n rows holds at most one queen, and n queens need exactly one per row. This turns the search into choosing a column per row.
  2. 2. Which value is constant along one diagonal direction?

    Moving one step down and one step right adds 1 to both row and col, leaving row - col unchanged. Along the other diagonal row + col stays constant.
  3. 3. How many solutions does the 6-Queens problem have?

    The counts for n = 1 to 8 are 1, 0, 0, 2, 10, 4, 40, 92, so n = 6 has 4 solutions.
  4. 4. What is the space complexity of the backtracking solver (excluding the list of results)?

    It keeps three sets and a queens list of at most n entries, and the recursion goes n levels deep.
  5. 5. What does the 'undo' step in N-Queens do?

    The sets are shared by all calls, so after exploring a column its column and diagonal entries must be removed before trying another.

Summary

  • N-Queens asks for n non-attacking queens on an n x n board; the counts for n = 1 to 8 are 1, 0, 0, 2, 10, 4, 40, 92.
  • Place one queen per row and choose a column; track columns, row - col diagonals and row + col anti-diagonals in sets for O(1) checks.
  • Choose, explore, undo with all three sets; copy the queens list when a solution is found.
  • Pruning cuts the search from millions of boards to a few thousand calls for n = 8, but it stays exponential.
  • Bitmasks make the same search faster; symmetry can halve it.

Next: Sudoku and Constraint Puzzles