I was going through this really neat solution for n-queen problem from Elements of Programming Interviews, Recursion chapter, but can't seem to understand a particular piece of code. If someone can explain the logic here, it would be really helpful. If condition for checking conflicts is something I am trying to wrap my head around here but to no success.
def n_queens(n: int) -> List[List[int]]:
def solve_n_queens(row):
if row == n:
# All queens are legally placed.
result.append(col_placement.copy())
return
for col in range(n):
# Test if a newly place queen will conflict any earlier queens place before
# I am struggling to make sense of this if condition
if all(abs(c - col) not in (0, row - i)
for i, c in enumerate(col_placement[:row])):
col_placement[row] = col
solve_n_queens(row + 1)
result: List[List[int]] = []
col_placement = [0] * n
solve_n_queens(0)
return result
Given that each row of the chessboard must have exactly one queen, the solution is represented as a list of horizontal-positions of the queens in each row. Furthermore, this list is built from top-to-bottom, so when a queen is inserted, it is the lowest queen so far, and all other queens on the board must be in rows above it.
Therefore to check for conflicts, there are only three directions to look: upwards in the same column, diagonally up and to the left, and diagonally up and to the right.
The condition all(abs(c - col) not in (0, row - i)) checks this, for each other queen on the board so far. The numbers i, c represent the vertical and horizontal position of each queen respectively; row, col represent the position of the queen currently being checked for conflicts.
c - col == 0.c - col == i - row.c - col == row - i.All three of these can be checked at once by taking c - col and testing if it is one of the three numbers (0, i - row, row - i). Using the absolute value function, this is equivalent to testing if abs(c - col) is one of the two non-negative numbers (0, row - i).