The N-Queens puzzle is a classic problem in which the goal is to place n queens on an n n chessboard so that no two queens can attack each other.
In chess, a queen can move any number of squares horizontally, vertically, or diagonally. Therefore, no two queens can be placed in the same row, column, or diagonal.
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:
n
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:
Define an empty 2D array, solutions, to store all distinct valid arrangements of n queens on the board.
Create an n n chessboard, board, where all cells initially contain '.'.
Create three helper arrays to track constraints and avoid conflicts:
cols of size n, initialized with FALSE. A TRUE value at cols[i] means column i already has a queen.
diag1 of size 2n - 1, initialized with FALSE. A TRUE at diag1[row + col] indicates the / diagonal is occupied. ...
The N-Queens puzzle is a classic problem in which the goal is to place n queens on an n n chessboard so that no two queens can attack each other.
In chess, a queen can move any number of squares horizontally, vertically, or diagonally. Therefore, no two queens can be placed in the same row, column, or diagonal.
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:
n
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:
Define an empty 2D array, solutions, to store all distinct valid arrangements of n queens on the board.
Create an n n chessboard, board, where all cells initially contain '.'.
Create three helper arrays to track constraints and avoid conflicts:
cols of size n, initialized with FALSE. A TRUE value at cols[i] means column i already has a queen.
diag1 of size 2n - 1, initialized with FALSE. A TRUE at diag1[row + col] indicates the / diagonal is occupied. ...