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

All Solutions

Finding one valid board is a good start, but the classic version of N Queens asks for every valid arrangement. A 4 × 4 board has two solutions:

[
    [1, 3, 0, 2],
    [2, 0, 3, 1],
]

But it starts to ramp up fast:

N	Solutions	Candidates
4	2	256
5	10	3,125
6	4	46,656
7	40	823,543
8	92	16,777,216
9	352	387,420,489
10	724	10,000,000,000
11	2,680	285,311,670,611
12	14,200	8,916,100,448,256

Collecting all the valid boards uses almost the same logic as just the first one. Instead of returning the moment we find a valid board, we store each one in a list and keep going until we've checked every candidate. The catch is the sheer number of candidate boards we generate along the way: it grows as n ** n, which you can also see in the table above.

On my machine, the memory and runtime of brute-forcing N Queens look roughly like this:

n = 7: 100 MiB RAM, 1 sec runtime
n = 8: 2 GiB RAM, 15 sec runtime
n = 9: Didn't even try, and don't recommend it

Performance will also be significantly worse in the in-browser Python environment.

So brute force works, but in later lessons, we'll do something smarter.

Assignment

Fix the solve_n_queens function. Instead of returning the first valid board, it should return a list of all valid boards.

Update the return type from list[int] to list[list[int]].
Create an empty list to store valid boards.
Check every candidate board. When a board is valid, add it to the list instead of returning it immediately.
Return the list of valid boards after checking every candidate.