Solution: N-Queens
Explore how to apply backtracking to solve the N-Queens puzzle by placing queens on an n×n board without conflicts. This lesson guides you through using helper arrays to track columns and diagonals, systematically building valid arrangements through recursion and backtracking. Understand the algorithm's time and space complexity to prepare for coding interviews.
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 ...