Solution: N-Queens
Explore a backtracking technique to solve the N-Queens problem by placing queens one row at a time on an n×n chessboard. Understand how to track column and diagonal constraints to ensure no queen attacks another, and learn the recursive process to find all valid solutions efficiently.
We'll cover the following...
Statement
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
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 ...