Backtracking

A backtracking algorithm begins with an empty solution and extends the solution step by step. The search recursively goes through all different ways how a solution can be constructed.

Queen problem

As an example, consider the problem of calculating the number of ways $n$ queens can be placed on an $n \times n$ chessboard so that no two queens attack each other. For example, when $n=4$, there are two possible solutions:

The problem can be solved using backtracking by placing queens to the board row by row. More precisely, exactly one queen will be placed on each row so that no queen attacks any of the queens placed before. A solution has been found when all $n$ queens have been placed on the board.

For example, when $n=4$, some partial solutions generated by the backtracking algorithm are as follows:

At the bottom level, the three first configurations are illegal, because the queens attack each other. However, the fourth configuration is valid and it can be extended to a complete solution by placing two more queens to the board. There is only one way to place the two remaining queens.

The algorithm can be implemented as follows:

#![allow(unused)]
fn main() {
let n = 4;
let mut count = 0;
let mut column = vec![false;n];
let mut diag1 = vec![false;2*n-1];
let mut diag2 = vec![false;2*n-1];
search(0, n, &mut count, &mut column, &mut diag1, &mut diag2);
println!{"{count}"};
fn search(y: usize, n: usize, count: &mut usize, column: &mut Vec<bool>, diag1: &mut Vec<bool>, diag2: &mut Vec<bool>) {
    if y == n {
        *count += 1;
        return;
    }
    for x in 0..n {
        if column[x] || diag1[x + y] || diag2[x.wrapping_sub(y).wrapping_add(n).wrapping_sub(1)] {
            continue;
        }
        column[x] = true;
        diag1[x + y] = true;
        diag2[x + n - y - 1] = true;
        search(y + 1, n, count, column, diag1, diag2);
        column[x] = false;
        diag1[x + y] = false;
        diag2[x + n - y - 1] = false;
    }
}
}

wrapping_sub is used to avoid that a negative number has used as usize

The search begins by calling search(0, n, &mut count, &mut column, &mut diag1, &mut diag2); The size of the board is $n \times n$, and the code calculates the number of solutions to count.

The code assumes that the rows and columns of the board are numbered from 0 to $n-1$. When the function search is called with parameter $y$, it places a queen on row $y$ and then calls itself with parameter $y+1$. Then, if $y=n$, a solution has been found and the variable count is increased by one.

The Vec column keeps track of columns that contain a queen, and the arrays diag1 and diag2 keep track of diagonals. It is not allowed to add another queen to a column or diagonal that already contains a queen. For example, the columns and diagonals of the $4 \times 4$ board are numbered as follows:

Let $q(n)$ denote the number of ways to place $n$ queens on an $n \times n$ chessboard. The above backtracking algorithm tells us that, for example, $q(8)=92$. When $n$ increases, the search quickly becomes slow, because the number of solutions increases exponentially. For example, calculating $q(16)=14772512$ using the above algorithm already takes about a minute on a modern computer¹

¹ There is no known way to efficiently calculate larger values of $q(n)$. The current record is $q(27)=234907967154122528$, calculated in 2016 [55].