13.4 N-queens problem¶
Question
In chess, a queen can attack any piece in the same row, column, or diagonal. Given \(n\) queens and an \(n \times n\) chessboard, find all arrangements in which no two queens can attack each other.
As shown in Figure 13-15, there are two solutions when \(n = 4\). From a backtracking perspective, the \(n \times n\) board has \(n^2\) squares, which provide all possible choices. As we place queens one by one, the board changes; its arrangement at any moment is the current state.
Figure 13-15 Solutions to the 4-queens problem
Figure 13-16 shows the three constraints: no two queens may share a row, column, or diagonal. Diagonals run in two directions: the main-diagonal direction \ and the antidiagonal direction /.
Figure 13-16 Constraints of the n-queens problem
1. Placing queens row by row¶
There are as many queens as rows, namely \(n\), so we can immediately conclude that each row must contain exactly one queen.
We can therefore place queens row by row: start at the first row and place one queen in each row through the last.
Figure 13-17 illustrates this process for 4 queens. To fit the illustration, only one branch from the first row is expanded, and all arrangements violating the column or diagonal constraints are pruned.
Figure 13-17 Placing queens row by row
In essence, placing queens row by row is itself a form of pruning: it eliminates every search branch that places multiple queens in the same row.
2. Pruning by columns and diagonals¶
To enforce the column constraint, use a Boolean array cols of length \(n\) to record whether each column contains a queen. Before placing a queen, consult cols to prune columns already occupied, and update cols as the search proceeds and backtracks.
Tip
The matrix starts at its top-left corner. Row indices increase downward, and column indices increase to the right.
How do we enforce the diagonal constraints? Let \((row, col)\) be the row and column indices of a square. Along any diagonal in the main-diagonal direction, the row index minus the column index is the same: \(row - col\) is constant along that diagonal.
Thus, if two squares satisfy \(row_1 - col_1 = row_2 - col_2\), they lie on the same main-direction diagonal. Using this property, the array diags1 in Figure 13-18 records whether each such diagonal contains a queen.
Similarly, \(row + col\) is constant along each antidiagonal. We can use an array diags2 to enforce the antidiagonal constraint.
Figure 13-18 Enforcing column and diagonal constraints
3. Code implementation¶
In a square matrix of order \(n\), \(row - col\) ranges over \([-n + 1, n - 1]\), and \(row + col\) ranges over \([0, 2n - 2]\). There are therefore \(2n - 1\) diagonals in each direction, so both diags1 and diags2 have length \(2n - 1\).
def backtrack(
row: int,
n: int,
state: list[list[str]],
res: list[list[list[str]]],
cols: list[bool],
diags1: list[bool],
diags2: list[bool],
):
"""Backtracking: n-queens"""
# Record a solution when a queen has been placed in every row
if row == n:
res.append([list(row) for row in state])
return
# Iterate over all columns
for col in range(n):
# Calculate the main-diagonal and anti-diagonal indices for this square
diag1 = row - col + n - 1
diag2 = row + col
# Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if not cols[col] and not diags1[diag1] and not diags2[diag2]:
# Try: place a queen on this square
state[row][col] = "Q"
cols[col] = diags1[diag1] = diags2[diag2] = True
# Place a queen in the next row
backtrack(row + 1, n, state, res, cols, diags1, diags2)
# Backtrack: restore this square to empty
state[row][col] = "#"
cols[col] = diags1[diag1] = diags2[diag2] = False
def n_queens(n: int) -> list[list[list[str]]]:
"""Solve the n-queens problem"""
# Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
state = [["#" for _ in range(n)] for _ in range(n)]
cols = [False] * n # Track whether a column contains a queen
diags1 = [False] * (2 * n - 1) # Track whether a main diagonal contains a queen
diags2 = [False] * (2 * n - 1) # Track whether an anti-diagonal contains a queen
res = []
backtrack(0, n, state, res, cols, diags1, diags2)
return res
/* Backtracking: n-queens */
void backtrack(int row, int n, vector<vector<string>> &state, vector<vector<vector<string>>> &res, vector<bool> &cols,
vector<bool> &diags1, vector<bool> &diags2) {
// Record a solution when a queen has been placed in every row
if (row == n) {
res.push_back(state);
return;
}
// Iterate over all columns
for (int col = 0; col < n; col++) {
// Calculate the main-diagonal and anti-diagonal indices for this square
int diag1 = row - col + n - 1;
int diag2 = row + col;
// Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
// Try: place a queen on this square
state[row][col] = "Q";
cols[col] = diags1[diag1] = diags2[diag2] = true;
// Place a queen in the next row
backtrack(row + 1, n, state, res, cols, diags1, diags2);
// Backtrack: restore this square to empty
state[row][col] = "#";
cols[col] = diags1[diag1] = diags2[diag2] = false;
}
}
}
/* Solve the n-queens problem */
vector<vector<vector<string>>> nQueens(int n) {
// Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
vector<vector<string>> state(n, vector<string>(n, "#"));
vector<bool> cols(n, false); // Track whether a column contains a queen
vector<bool> diags1(2 * n - 1, false); // Track whether a main diagonal contains a queen
vector<bool> diags2(2 * n - 1, false); // Track whether an anti-diagonal contains a queen
vector<vector<vector<string>>> res;
backtrack(0, n, state, res, cols, diags1, diags2);
return res;
}
/* Backtracking: n-queens */
void backtrack(int row, int n, List<List<String>> state, List<List<List<String>>> res,
boolean[] cols, boolean[] diags1, boolean[] diags2) {
// Record a solution when a queen has been placed in every row
if (row == n) {
List<List<String>> copyState = new ArrayList<>();
for (List<String> sRow : state) {
copyState.add(new ArrayList<>(sRow));
}
res.add(copyState);
return;
}
// Iterate over all columns
for (int col = 0; col < n; col++) {
// Calculate the main-diagonal and anti-diagonal indices for this square
int diag1 = row - col + n - 1;
int diag2 = row + col;
// Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
// Try: place a queen on this square
state.get(row).set(col, "Q");
cols[col] = diags1[diag1] = diags2[diag2] = true;
// Place a queen in the next row
backtrack(row + 1, n, state, res, cols, diags1, diags2);
// Backtrack: restore this square to empty
state.get(row).set(col, "#");
cols[col] = diags1[diag1] = diags2[diag2] = false;
}
}
}
/* Solve the n-queens problem */
List<List<List<String>>> nQueens(int n) {
// Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
List<List<String>> state = new ArrayList<>();
for (int i = 0; i < n; i++) {
List<String> row = new ArrayList<>();
for (int j = 0; j < n; j++) {
row.add("#");
}
state.add(row);
}
boolean[] cols = new boolean[n]; // Track whether a column contains a queen
boolean[] diags1 = new boolean[2 * n - 1]; // Track whether a main diagonal contains a queen
boolean[] diags2 = new boolean[2 * n - 1]; // Track whether an anti-diagonal contains a queen
List<List<List<String>>> res = new ArrayList<>();
backtrack(0, n, state, res, cols, diags1, diags2);
return res;
}
/* Backtracking: n-queens */
void Backtrack(int row, int n, List<List<string>> state, List<List<List<string>>> res,
bool[] cols, bool[] diags1, bool[] diags2) {
// Record a solution when a queen has been placed in every row
if (row == n) {
List<List<string>> copyState = [];
foreach (List<string> sRow in state) {
copyState.Add(new List<string>(sRow));
}
res.Add(copyState);
return;
}
// Iterate over all columns
for (int col = 0; col < n; col++) {
// Calculate the main-diagonal and anti-diagonal indices for this square
int diag1 = row - col + n - 1;
int diag2 = row + col;
// Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
// Try: place a queen on this square
state[row][col] = "Q";
cols[col] = diags1[diag1] = diags2[diag2] = true;
// Place a queen in the next row
Backtrack(row + 1, n, state, res, cols, diags1, diags2);
// Backtrack: restore this square to empty
state[row][col] = "#";
cols[col] = diags1[diag1] = diags2[diag2] = false;
}
}
}
/* Solve the n-queens problem */
List<List<List<string>>> NQueens(int n) {
// Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
List<List<string>> state = [];
for (int i = 0; i < n; i++) {
List<string> row = [];
for (int j = 0; j < n; j++) {
row.Add("#");
}
state.Add(row);
}
bool[] cols = new bool[n]; // Track whether a column contains a queen
bool[] diags1 = new bool[2 * n - 1]; // Track whether a main diagonal contains a queen
bool[] diags2 = new bool[2 * n - 1]; // Track whether an anti-diagonal contains a queen
List<List<List<string>>> res = [];
Backtrack(0, n, state, res, cols, diags1, diags2);
return res;
}
/* Backtracking: n-queens */
func backtrack(row, n int, state *[][]string, res *[][][]string, cols, diags1, diags2 *[]bool) {
// Record a solution when a queen has been placed in every row
if row == n {
newState := make([][]string, len(*state))
for i, _ := range newState {
newState[i] = make([]string, len((*state)[0]))
copy(newState[i], (*state)[i])
}
*res = append(*res, newState)
return
}
// Iterate over all columns
for col := 0; col < n; col++ {
// Calculate the main-diagonal and anti-diagonal indices for this square
diag1 := row - col + n - 1
diag2 := row + col
// Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if !(*cols)[col] && !(*diags1)[diag1] && !(*diags2)[diag2] {
// Try: place a queen on this square
(*state)[row][col] = "Q"
(*cols)[col], (*diags1)[diag1], (*diags2)[diag2] = true, true, true
// Place a queen in the next row
backtrack(row+1, n, state, res, cols, diags1, diags2)
// Backtrack: restore this square to empty
(*state)[row][col] = "#"
(*cols)[col], (*diags1)[diag1], (*diags2)[diag2] = false, false, false
}
}
}
/* Solve the n-queens problem */
func nQueens(n int) [][][]string {
// Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
state := make([][]string, n)
for i := 0; i < n; i++ {
row := make([]string, n)
for i := 0; i < n; i++ {
row[i] = "#"
}
state[i] = row
}
// Track whether a column contains a queen
cols := make([]bool, n)
diags1 := make([]bool, 2*n-1)
diags2 := make([]bool, 2*n-1)
res := make([][][]string, 0)
backtrack(0, n, &state, &res, &cols, &diags1, &diags2)
return res
}
/* Backtracking: n-queens */
func backtrack(row: Int, n: Int, state: inout [[String]], res: inout [[[String]]], cols: inout [Bool], diags1: inout [Bool], diags2: inout [Bool]) {
// Record a solution when a queen has been placed in every row
if row == n {
res.append(state)
return
}
// Iterate over all columns
for col in 0 ..< n {
// Calculate the main-diagonal and anti-diagonal indices for this square
let diag1 = row - col + n - 1
let diag2 = row + col
// Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if !cols[col] && !diags1[diag1] && !diags2[diag2] {
// Try: place a queen on this square
state[row][col] = "Q"
cols[col] = true
diags1[diag1] = true
diags2[diag2] = true
// Place a queen in the next row
backtrack(row: row + 1, n: n, state: &state, res: &res, cols: &cols, diags1: &diags1, diags2: &diags2)
// Backtrack: restore this square to empty
state[row][col] = "#"
cols[col] = false
diags1[diag1] = false
diags2[diag2] = false
}
}
}
/* Solve the n-queens problem */
func nQueens(n: Int) -> [[[String]]] {
// Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
var state = Array(repeating: Array(repeating: "#", count: n), count: n)
var cols = Array(repeating: false, count: n) // Track whether a column contains a queen
var diags1 = Array(repeating: false, count: 2 * n - 1) // Track whether a main diagonal contains a queen
var diags2 = Array(repeating: false, count: 2 * n - 1) // Track whether an anti-diagonal contains a queen
var res: [[[String]]] = []
backtrack(row: 0, n: n, state: &state, res: &res, cols: &cols, diags1: &diags1, diags2: &diags2)
return res
}
/* Backtracking: n-queens */
function backtrack(row, n, state, res, cols, diags1, diags2) {
// Record a solution when a queen has been placed in every row
if (row === n) {
res.push(state.map((row) => row.slice()));
return;
}
// Iterate over all columns
for (let col = 0; col < n; col++) {
// Calculate the main-diagonal and anti-diagonal indices for this square
const diag1 = row - col + n - 1;
const diag2 = row + col;
// Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
// Try: place a queen on this square
state[row][col] = 'Q';
cols[col] = diags1[diag1] = diags2[diag2] = true;
// Place a queen in the next row
backtrack(row + 1, n, state, res, cols, diags1, diags2);
// Backtrack: restore this square to empty
state[row][col] = '#';
cols[col] = diags1[diag1] = diags2[diag2] = false;
}
}
}
/* Solve the n-queens problem */
function nQueens(n) {
// Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
const state = Array.from({ length: n }, () => Array(n).fill('#'));
const cols = Array(n).fill(false); // Track whether a column contains a queen
const diags1 = Array(2 * n - 1).fill(false); // Track whether a main diagonal contains a queen
const diags2 = Array(2 * n - 1).fill(false); // Track whether an anti-diagonal contains a queen
const res = [];
backtrack(0, n, state, res, cols, diags1, diags2);
return res;
}
/* Backtracking: n-queens */
function backtrack(
row: number,
n: number,
state: string[][],
res: string[][][],
cols: boolean[],
diags1: boolean[],
diags2: boolean[]
): void {
// Record a solution when a queen has been placed in every row
if (row === n) {
res.push(state.map((row) => row.slice()));
return;
}
// Iterate over all columns
for (let col = 0; col < n; col++) {
// Calculate the main-diagonal and anti-diagonal indices for this square
const diag1 = row - col + n - 1;
const diag2 = row + col;
// Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
// Try: place a queen on this square
state[row][col] = 'Q';
cols[col] = diags1[diag1] = diags2[diag2] = true;
// Place a queen in the next row
backtrack(row + 1, n, state, res, cols, diags1, diags2);
// Backtrack: restore this square to empty
state[row][col] = '#';
cols[col] = diags1[diag1] = diags2[diag2] = false;
}
}
}
/* Solve the n-queens problem */
function nQueens(n: number): string[][][] {
// Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
const state = Array.from({ length: n }, () => Array(n).fill('#'));
const cols = Array(n).fill(false); // Track whether a column contains a queen
const diags1 = Array(2 * n - 1).fill(false); // Track whether a main diagonal contains a queen
const diags2 = Array(2 * n - 1).fill(false); // Track whether an anti-diagonal contains a queen
const res: string[][][] = [];
backtrack(0, n, state, res, cols, diags1, diags2);
return res;
}
/* Backtracking: n-queens */
void backtrack(
int row,
int n,
List<List<String>> state,
List<List<List<String>>> res,
List<bool> cols,
List<bool> diags1,
List<bool> diags2,
) {
// Record a solution when a queen has been placed in every row
if (row == n) {
List<List<String>> copyState = [];
for (List<String> sRow in state) {
copyState.add(List.from(sRow));
}
res.add(copyState);
return;
}
// Iterate over all columns
for (int col = 0; col < n; col++) {
// Calculate the main-diagonal and anti-diagonal indices for this square
int diag1 = row - col + n - 1;
int diag2 = row + col;
// Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
// Try: place a queen on this square
state[row][col] = "Q";
cols[col] = true;
diags1[diag1] = true;
diags2[diag2] = true;
// Place a queen in the next row
backtrack(row + 1, n, state, res, cols, diags1, diags2);
// Backtrack: restore this square to empty
state[row][col] = "#";
cols[col] = false;
diags1[diag1] = false;
diags2[diag2] = false;
}
}
}
/* Solve the n-queens problem */
List<List<List<String>>> nQueens(int n) {
// Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
List<List<String>> state = List.generate(n, (index) => List.filled(n, "#"));
List<bool> cols = List.filled(n, false); // Track whether a column contains a queen
List<bool> diags1 = List.filled(2 * n - 1, false); // Track whether a main diagonal contains a queen
List<bool> diags2 = List.filled(2 * n - 1, false); // Track whether an anti-diagonal contains a queen
List<List<List<String>>> res = [];
backtrack(0, n, state, res, cols, diags1, diags2);
return res;
}
/* Backtracking: n-queens */
fn backtrack(
row: usize,
n: usize,
state: &mut Vec<Vec<String>>,
res: &mut Vec<Vec<Vec<String>>>,
cols: &mut [bool],
diags1: &mut [bool],
diags2: &mut [bool],
) {
// Record a solution when a queen has been placed in every row
if row == n {
res.push(state.clone());
return;
}
// Iterate over all columns
for col in 0..n {
// Calculate the main-diagonal and anti-diagonal indices for this square
let diag1 = row + n - 1 - col;
let diag2 = row + col;
// Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if !cols[col] && !diags1[diag1] && !diags2[diag2] {
// Try: place a queen on this square
state[row][col] = "Q".into();
(cols[col], diags1[diag1], diags2[diag2]) = (true, true, true);
// Place a queen in the next row
backtrack(row + 1, n, state, res, cols, diags1, diags2);
// Backtrack: restore this square to empty
state[row][col] = "#".into();
(cols[col], diags1[diag1], diags2[diag2]) = (false, false, false);
}
}
}
/* Solve the n-queens problem */
fn n_queens(n: usize) -> Vec<Vec<Vec<String>>> {
// Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
let mut state: Vec<Vec<String>> = vec![vec!["#".to_string(); n]; n];
let mut cols = vec![false; n]; // Track whether a column contains a queen
let mut diags1 = vec![false; 2 * n - 1]; // Track whether a main diagonal contains a queen
let mut diags2 = vec![false; 2 * n - 1]; // Track whether an anti-diagonal contains a queen
let mut res: Vec<Vec<Vec<String>>> = Vec::new();
backtrack(
0,
n,
&mut state,
&mut res,
&mut cols,
&mut diags1,
&mut diags2,
);
res
}
/* Backtracking: n-queens */
void backtrack(int row, int n, char state[MAX_SIZE][MAX_SIZE], char ***res, int *resSize, bool cols[MAX_SIZE],
bool diags1[2 * MAX_SIZE - 1], bool diags2[2 * MAX_SIZE - 1]) {
// Record a solution when a queen has been placed in every row
if (row == n) {
res[*resSize] = (char **)malloc(sizeof(char *) * n);
for (int i = 0; i < n; ++i) {
res[*resSize][i] = (char *)malloc(sizeof(char) * (n + 1));
strcpy(res[*resSize][i], state[i]);
}
(*resSize)++;
return;
}
// Iterate over all columns
for (int col = 0; col < n; col++) {
// Calculate the main-diagonal and anti-diagonal indices for this square
int diag1 = row - col + n - 1;
int diag2 = row + col;
// Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
// Try: place a queen on this square
state[row][col] = 'Q';
cols[col] = diags1[diag1] = diags2[diag2] = true;
// Place a queen in the next row
backtrack(row + 1, n, state, res, resSize, cols, diags1, diags2);
// Backtrack: restore this square to empty
state[row][col] = '#';
cols[col] = diags1[diag1] = diags2[diag2] = false;
}
}
}
/* Solve the n-queens problem */
char ***nQueens(int n, int *returnSize) {
char state[MAX_SIZE][MAX_SIZE];
// Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
state[i][j] = '#';
}
state[i][n] = '\0';
}
bool cols[MAX_SIZE] = {false}; // Track whether a column contains a queen
bool diags1[2 * MAX_SIZE - 1] = {false}; // Track whether a main diagonal contains a queen
bool diags2[2 * MAX_SIZE - 1] = {false}; // Track whether an anti-diagonal contains a queen
char ***res = (char ***)malloc(sizeof(char **) * MAX_SIZE);
*returnSize = 0;
backtrack(0, n, state, res, returnSize, cols, diags1, diags2);
return res;
}
/* Backtracking: n-queens */
fun backtrack(
row: Int,
n: Int,
state: MutableList<MutableList<String>>,
res: MutableList<MutableList<MutableList<String>>?>,
cols: BooleanArray,
diags1: BooleanArray,
diags2: BooleanArray
) {
// Record a solution when a queen has been placed in every row
if (row == n) {
val copyState = mutableListOf<MutableList<String>>()
for (sRow in state) {
copyState.add(sRow.toMutableList())
}
res.add(copyState)
return
}
// Iterate over all columns
for (col in 0..<n) {
// Calculate the main-diagonal and anti-diagonal indices for this square
val diag1 = row - col + n - 1
val diag2 = row + col
// Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
// Try: place a queen on this square
state[row][col] = "Q"
diags2[diag2] = true
diags1[diag1] = diags2[diag2]
cols[col] = diags1[diag1]
// Place a queen in the next row
backtrack(row + 1, n, state, res, cols, diags1, diags2)
// Backtrack: restore this square to empty
state[row][col] = "#"
diags2[diag2] = false
diags1[diag1] = diags2[diag2]
cols[col] = diags1[diag1]
}
}
}
/* Solve the n-queens problem */
fun nQueens(n: Int): MutableList<MutableList<MutableList<String>>?> {
// Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
val state = mutableListOf<MutableList<String>>()
for (i in 0..<n) {
val row = mutableListOf<String>()
for (j in 0..<n) {
row.add("#")
}
state.add(row)
}
val cols = BooleanArray(n) // Track whether a column contains a queen
val diags1 = BooleanArray(2 * n - 1) // Track whether a main diagonal contains a queen
val diags2 = BooleanArray(2 * n - 1) // Track whether an anti-diagonal contains a queen
val res = mutableListOf<MutableList<MutableList<String>>?>()
backtrack(0, n, state, res, cols, diags1, diags2)
return res
}
### Backtracking: n-queens ###
def backtrack(row, n, state, res, cols, diags1, diags2)
# Record a solution when a queen has been placed in every row
if row == n
res << state.map { |row| row.dup }
return
end
# Iterate over all columns
for col in 0...n
# Calculate the main-diagonal and anti-diagonal indices for this square
diag1 = row - col + n - 1
diag2 = row + col
# Prune: the square must have no queen in its column, main diagonal, or anti-diagonal
if !cols[col] && !diags1[diag1] && !diags2[diag2]
# Try: place a queen on this square
state[row][col] = "Q"
cols[col] = diags1[diag1] = diags2[diag2] = true
# Place a queen in the next row
backtrack(row + 1, n, state, res, cols, diags1, diags2)
# Backtrack: restore this square to empty
state[row][col] = "#"
cols[col] = diags1[diag1] = diags2[diag2] = false
end
end
end
### Solve the n-queens problem ###
def n_queens(n)
# Initialize an n*n board, where 'Q' represents a queen and '#' represents an empty square
state = Array.new(n) { Array.new(n, "#") }
cols = Array.new(n, false) # Track whether a column contains a queen
diags1 = Array.new(2 * n - 1, false) # Track whether a main diagonal contains a queen
diags2 = Array.new(2 * n - 1, false) # Track whether an anti-diagonal contains a queen
res = []
backtrack(0, n, state, res, cols, diags1, diags2)
res
end
Visualize execution
We place a queen in each of \(n\) rows. Considering the column constraint, the successive rows have \(n\), \(n-1\), \(\dots\), \(2\), and \(1\) choices, giving \(O(n!)\) time. Recording a solution requires copying the matrix state and appending the copy to res, which takes \(O(n^2)\) time. The overall time complexity is therefore \(O(n! \cdot n^2)\). In practice, diagonal pruning greatly reduces the search space, so the search is often faster than this bound suggests.
The array state uses \(O(n^2)\) space, while cols, diags1, and diags2 each use \(O(n)\) space. The maximum recursion depth is \(n\), requiring \(O(n)\) space for stack frames. The space complexity is therefore \(O(n^2)\).