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

First Solution

We already have the logic needed to solve N Queens in a blunt way:

Generate every candidate board.
Check the validity of each one.
Return a list of all the valid boards – or, for an easier version of the problem, return any valid board.

This is a brute force solution. We're not being clever, we're just searching through the entire space of possibilities until we find an answer.

For n = 4, the first valid board we hit while checking candidates in lexicographic order is:

[1, 3, 0, 2]

Which represents the board you're probably tired of seeing by now:

Not every board size has a solution. There's no way to solve N Queens on a 2 × 2 or 3 × 3 board, so the correct answer in those cases is an empty list ([]).

Assignment

Complete the solve_n_queens function. It accepts a board size n and returns the first valid board it finds, or an empty list if no valid board exists.

The get_candidate_boards and is_valid_board functions are provided for you.

Use get_candidate_boards to generate a list of board arrangements to check.
Iterate over the candidate boards:
1. Use is_valid_board to check each one.
2. If you find a valid board, return it immediately. Because the candidates are already ordered, this will be the "first" solution.
If no valid board was found, return an empty list.

We won't test anything beyond n = 7 here, since the brute-force approach of generating all possible candidate boards requires exponentially increasing amounts of memory.

Running this with n = 8 would try to allocate more than 2 GB!