CODEWITHSUNDEEP
python-3.xrecursionbacktrackingn-queens
Mr Matrix
Mr Matrix

Reputation: 1278

Python N-Queen solution explanation

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

Upvotes: 2

Views: 515

Answers (2)

EdW
EdW

Reputation: 2293

The test at the bottom checks each previous queen placement to see:

  1. if the previous queen column placement == current column placement
  2. if the slope: abs(current column - previous column)/(current row - previous row) == 1

To clarify, let's change the variable names and the test, containing two comparisons for each previous row, is now written:

if all(abs(prev_col - curr_col) not in (0, curr_row - prev_row)
            for prev_row, prev_col in enumerate(col_placement[:row])):
  1. above is prev_col - curr_col != 0 #queens are not in the same column

For 2., since a chess board is a square, all diagonal slopes will equal one. A slope of one can be tested by insuring delta y = delta x. For example 2/2 = 1, so 2 == 2.

For the rewritten test above, the test is: abs(prev_col - curr_col) != curr_row - prev_row. abs() for the columns insures both diagonal directions are tested; abs() is not needed for rows since curr_row is the last row added.

        # 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])):

Upvotes: 0

kaya3
kaya3

Reputation: 51063

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.

  • A conflict in the same column means c - col == 0.
  • A conflict diagonally up and to the left means c - col == i - row.
  • A conflict diagonally up and to the right means 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).

Upvotes: 5

Related Questions