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 ...