This lesson's interactive features are locked, please to keep using them

Pruning

Backtracking is way better than brute force, but it's still doing extra work on every move. Each time we consider a new queen position, is_safe loops over the whole board to ask:

Is this column already used?
Is this diagonal already used?

While that's cheap on a small board, each check gets slower as the partial board grows. We can make the same decision faster by tracking which columns and diagonals are already taken.

We're already pruning the tree of possible boards by cutting off branches the moment we know they can't work. Now we're just going to make each of those pruning checks cheaper.

Used Columns

Columns are simple. Once we place a queen in column 3, column 3 is off-limits for every future row.

We can track the used columns with a set:

used_cols = set()

And the column check collapses to a single lookup:

col in used_cols

Used Diagonals

Diagonals are a bit more complicated, but they follow patterns that we can use.

For one diagonal direction, going up and to the right, every square on the same diagonal has the same row + col value:

row + col = 2

The (row, col) values and their sums:

(0, 2) → 0 + 2 = 2
(1, 1) → 1 + 1 = 2
(2, 0) → 2 + 0 = 2

For the other direction, going down and to the right, every square on the same diagonal has the same row - col value:

row - col = -1

The (row, col) values and their differences:

(0, 1) → 0 - 1 = -1
(1, 2) → 1 - 2 = -1
(2, 3) → 2 - 3 = -1

So we can catch a diagonal conflict by checking row + col against a set of used "up diagonals," and row - col against a set of used "down diagonals":

row + col in used_up_diagonals
row - col in used_down_diagonals

Combined Checks

Put it all together and testing a (row, col) position is three quick lookups – one for the column, two for the diagonals:

col in used_cols
row + col in used_up_diagonals
row - col in used_down_diagonals

Look ma, no loops!

Add and Remove

The backtracking pattern stays the same:

Make a choice.
Explore it recursively.
Undo the choice.

We'll just need to update the sets alongside the board. When we place a queen:

board.append(col)
used_cols.add(col)
used_up_diagonals.add(row + col)
used_down_diagonals.add(row - col)

And after the recursive call, we undo all of it:

board.pop()
used_cols.remove(col)
used_up_diagonals.remove(row + col)
used_down_diagonals.remove(row - col)

This way, the current board and the "used" sets stay in sync.

Assignment

Complete the solve_n_queens function, using backtracking with more efficient pruning. The function accepts a board size n (int) and returns all valid board arrangements (list[list[int]]).

Create an empty list to hold solutions.
Create an empty list to represent the current partial board.
Create three empty sets of integers:
- Used columns
- Used row + col diagonals
- Used row - col diagonals
Define a recursive backtrack helper function, inside solve_n_queens, which accepts the current row number and returns nothing. It should:
1. Check if the row is equal to n. If so, the current board is a solution; append a copy of it to the solutions list and return (from backtrack to its caller).
2. Otherwise, loop over columns, and for each column value:
  1. Calculate the row + col diagonal value.
  2. Calculate the row - col diagonal value.
  3. If the column or either diagonal is already used, continue to the next column value.
  4. Otherwise, append the column to the current board, and add the column and diagonal values to their sets.
  5. Recursively call backtrack for the next row.
  6. After that recursive call returns, pop() a column value from the board, and remove the same column and diagonal values from their sets so the next branch starts clean.
Start the search by calling backtrack(0).
Return the filled-in list of solutions.

This implementation gives another performance boost, so we can try larger values of n. The test cases go up to n = 12, which has well over 10,000 solutions!