Solution: N-Queens

Statement

The N-Queens puzzle is a classic problem in which the goal is to place n queens on an n $\times$ n chessboard so that no two queens can attack each other.

Given an integer n, return all distinct valid arrangements of n queens on the board. Each arrangement should be represented as a list of strings, where each string corresponds to a row of the board. Within each string, 'Q' denotes a queen and '.' denotes an empty square.

Note: You can return the solutions in any order.

Constraints:

• $1 \leq$ n $\leq 9$

Solution

The core idea behind the solution is to place queens one row at a time so that no two queens attack each other. As each queen must be in a unique row, we only need to decide which column to place the queen in for each row. To efficiently detect conflicts, we maintain three helper arrays: to track occupied columns, for '/' diagonals, and one for '\' diagonals. These arrays are updated whenever a queen is placed—marking the corresponding column and diagonals as occupied—and reset when the queen is removed.

At each recursion step, we iterate over all columns in the current row and try placing a queen in every safe position. If a position is valid, we place the queen, update the helper arrays, and recursively attempt to solve the next row. When we reach row n, a valid arrangement is complete, and we record the board as a solution. By backtracking, i.e., undoing the last placement and continuing with the next column, the algorithm systematically explores all possible board configurations, ensuring that all distinct valid solutions are found.

Using the intuition above, we implement the algorithm as follows:

1. Define an empty 2D array, solutions, to store all distinct valid arrangements of n queens on the board.

2. Create an n $\times$ n chessboard, board, where all cells initially contain '.'.

3. Create three helper arrays to track constraints and avoid conflicts:

   1. cols of size n, initialized with FALSE. A TRUE value at cols[i] means column i already has a queen.

   2. diag1 of size 2n - 1, initialized with FALSE. A TRUE at diag1[row + col] indicates the / diagonal is occupied.

   3. diag2 of size 2n - 1, initialized with FALSE. A TRUE at diag2[row - col + n - 1] indicates the \ diagonal is occupied.

4. Start backtracking from row 0 using the backtrack function with parameters: row, n, board, solutions, cols, diag1, and diag2.

The backtracking function is implemented as follows:

1. (Base case) If row == n, a valid arrangement has been formed.

   1. Add a copy of the current board to the solutions.

   2. Return to explore other possibilities.

2. For each column from 0 to n - 1:

   1. Check if placing a queen at (row, col) is safe:

      1. If any of cols[col], diag1[row + col], or diag2[row - col + n - 1] is TRUE, then placing a queen here would lead to a conflict. Skip this column.

   2. If it’s safe, place the queen: board[row][col] = 'Q'.

   3. Mark this column and both diagonals as occupied by setting: cols[col] $=$ diag1[row + col] $=$ diag2[row - col + n - 1] $=$ TRUE.

   4. Recur to the next row by calling backtrack with row + 1 to place the next queen.

   5. Backtrack after returning by removing the queen: board[row][col] = '.'.

   6. Unmark the column and diagonals as unoccupied: cols[col] $=$ diag1[row + col] $=$ diag2[row - col + n - 1] $=$ FALSE.

3. After exploring all possibilities, return solutions as a list of valid arrangements of n queens on the board.

Let’s look at the following illustration to get a better understanding of the solution: