Skip to content

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.

Solutions to the 4-queens problemSolutions to the 4-queens problem

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

Constraints of the n-queens problemConstraints of the n-queens problem

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.

Placing queens row by rowPlacing queens row by row

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.

Enforcing column and diagonal constraintsEnforcing column and diagonal constraints

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

n_queens.py
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
n_queens.cpp
/* 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;
}
n_queens.java
/* 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;
}
n_queens.cs
/* 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;
}
n_queens.go
/* 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
}
n_queens.swift
/* 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
}
n_queens.js
/* 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;
}
n_queens.ts
/* 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;
}
n_queens.dart
/* 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;
}
n_queens.rs
/* 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
}
n_queens.c
/* 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;
}
n_queens.kt
/* 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
}
n_queens.rb
### 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)\).

Share your insights, questions, or suggestions in the comments