This lesson's interactive features are locked, please to keep using them
Validate Boards
Generating all the candidate n × n boards is a small win, but most of those boards are junk – queens attacking each other all over the place. We need a way to separate the good boards from the bad ones.
Given a board layout represented by a list of column positions:
[1, 3, 0, 2]
The queens are arranged like this:
Because our candidate boards always place exactly one queen in each row, we get to skip checking for row conflicts entirely. That leaves just two ways for two queens to attack each other:
- They share a column
- They share a diagonal
Columns
Columns are the easy case. If two rows hold the same column value, the board is invalid:
[1, 3, 1, 2]
Rows 0 and 2 both have a queen in column 1, so those two queens can attack each other... so any board list with a repeated value is invalid.
Diagonals
Diagonals are a little trickier, but there's still a simple pattern. Two queens sit on the same diagonal when the distance between their rows equals the distance between their columns. For example:
[0, 1, 2, 3]
The queen in row 0, column 0 can attack the queen in row 1, column 1 (and vice versa):
row_distance = abs(0 - 1) # 1
col_distance = abs(0 - 1) # 1
The row distance and column distance are equal, so the two queens are on the same diagonal. For any pair of queens at (row_a, col_a) and (row_b, col_b), the diagonal check is just:
abs(row_a - row_b) == abs(col_a - col_b)
Assignment
Complete the is_valid_board function. It accepts a candidate board (list[int]) and returns a boolean: True if no queens can attack each other, otherwise False.