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

Backtracking

Now that we can check a position before committing to it, we don't have to build every board up front. Instead, we'll continuously build a single board, one row at a time:

Try a column in the current row.
If it's safe, place a queen there.
Move on to the next row.
If that path stops working, remove the queen and try the next column.

That "make a move, and undo it if it doesn't pan out" pattern is called backtracking.

Building and Undoing

Backtracking is a recursive search. We make a choice, explore everything that follows from it, and then undo it before trying the next option. The partial board still uses the same list representation:

board = [1, 3]

We've placed queens in rows 0 and 1, so the next recursive call handles row 2. If column 0 is safe, we place the queen:

board.append(0)

# [1, 3, 0]

Once we've explored every solution that starts with [1, 3, 0], we undo that choice:

board.pop()

# [1, 3]

Now we're free to try the next column for row 2.

Base Case

The search is done when we've placed a queen in every row. The moment row == n, the current board is a complete solution, and we save it and move on to the other options.

Because we keep mutating that same board list as the search goes, when we find a solution we have to save a copy of it:

solutions.append(board.copy())

This is a quirk of Python's memory model. If we appended board directly, every saved solution would point at the same list object, and they'd all change together as we kept going. Not what we want!

Assignment

Complete the solve_n_queens function, using recursive backtracking to build solutions one row at a time. The function accepts a board size n and returns all valid board arrangements.

Create an empty list to hold solutions.
Create an empty list to represent the current partial board. We'll spend the entire function mutating this one list as we explore different possibilities.
Define a recursive backtrack helper function, inside solve_n_queens, that accepts the current row number and returns nothing. It should:
1. Check if the given 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, for each column value:
  1. Call the provided is_safe function to see if the next position would be safe. If so:
    1. Append the column value to the current board.
    2. Recursively call backtrack for the next row, i.e., incrementing the row value by 1.
    3. After that recursive call returns, pop() a column value from the current board to undo the last choice before trying another column.
  2. Otherwise, skip it and check the next column.
Start the search by calling backtrack(0).
Return the filled-in list of solutions.

With the brute-force approach, we couldn't even safely try n = 9. With backtracking, we can handle n = 10 without breaking a sweat in terms of memory or runtime. Nice.