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

N Queens

The N Queens problem is a classic for a reason. It has a reputation for being nasty, and often shows up in software engineering interviews.

N Queens is useful because it's the perfect excuse to practice a core DS&A pattern: hunting through many possible states while leaning on constraints, backtracking, and pruning to skip work we don't need to do. Here's the question:

How can we place n queens on an n × n chessboard so that no two queens can attack each other?

The queen is the most powerful chess piece. She can attack anywhere along:

Her row
Her column
Both diagonals

For a tiny 4 × 4 board, one arrangement of queens that solves the problem looks like this:

No two queens share a row, column, or diagonal.

Sounds easy, right? Right...

Search Space

Here's our first constraint: a valid solution has exactly one queen in each row. If two queens shared a row, they'd be attacking each other before we even got started.

So, a simple brute-force search can go row by row:

One queen in row 0
One queen in row 1
One queen in row 2
And so on...

Each row has n possible columns. So the number of boards we might build before checking which ones actually pass is:

n * n * n * ... * n

Or, more compactly:

n**n

For an 8 × 8 board, that's 16,777,216 arrangements, and it only gets worse from here! The whole point of this challenge is to avoid as much of that work as we possibly can.

Representing the Board

We'll represent a "candidate board" as a list of column positions. Each index in the list is a row, and the value at that index is the column where the queen sits in that row. Again, this board:

Will be represented as:

[1, 3, 0, 2]

Row 0 has a queen in column 1
Row 1 has a queen in column 3
Row 2 has a queen in column 0
Row 3 has a queen in column 2

Assignment

Complete the get_candidate_boards function. It accepts a board size n (an int) and returns every possible board with exactly one queen in each row (a list[list[int]]).

The boards should be in lexicographic order, which happens naturally if you build them row by row and try columns from left to right. For example, if n=2, the return value should be:

[
    [0, 0],
    [0, 1],
    [1, 0],
    [1, 1],
]

Initialize a list of the "current" board arrangements, starting with a single empty board: [[]]
For each row in the given n:
1. Create an empty list for the next batch of candidate boards.
2. For each current candidate board so far:
  - For each column in the given n:
    - Create the "next board" by adding the column number to the end of the current candidate board. Make a new list here; don't mutate the current board in place, or later candidates will interfere with each other.
    - Append the "next board" to the list of next candidate boards.
3. Replace the old (current) list of board arrangements with the new list.
Return the final list of candidate boards.