n_queens.md

Generate All Nonattacking Placements of n-Queens

Given n queens on an n × n chessboard, compute all nonattacking placements.

Nonattacking placement = no two queens can threaten each other:

1. Queens can't be in same row
2. Queens can't be in same column
3. Queens can't be in same diagonal

Example

 Input: n = 4
Output: [[1, 3, 0, 2], [2, 0, 3, 1]]

A	B
♛ ♛ ♛ ♛	♛ ♛ ♛ ♛

Solution

def n_queens(n):
    def dfs(queens, xy_diff, xy_sum):
        row = len(queens)
        if row == n:
            result.append(queens)
        for col in range(n):
            if col not in queens and row - col not in xy_diff and row + col not in xy_sum:
                dfs(queens + [col], xy_diff + [row - col], xy_sum + [row + col])
    result = []
    dfs([], [], [])
    return result

Explanation

• For any point (x, y), if the new point (p, q) shouldn't share the same row, column, or diagonal, then we must have:
  1. p + q != x + y: eliminate left bottom right top diagonal
  2. p - q != x - y: eliminate left top right bottom diagonal

Code Dissection - dfs

1. Set the row as the length of queens, which is the list of column index per row

   row = len(queens)

2. If the current row is equal to n, then add it to queens

   if row == n:
       result.append(queens)

3. For any point (x, y), find a new point (p, q) that does not share the same row, column, or diagonal

   for col in range(n):
       if col not in queens and row - col not in xy_diff and row + col not in xy_sum:
           dfs(queens + [col], xy_diff + [row - col], xy_sum + [row + col])

   • queens the list of column index per row
   • row the current row where we're searching for a valid column
   • xy_diff the list of x - y
   • xy_sum the list of x + y

Code Dissection - n_queens

1. Create a list to hold the result, run dfs() with empty lists as the input, then return the result

   result = []
   dfs([], [], [])
   return result