Backtracking

Backtracking lists every arrangement that obeys a rule: every order of some numbers, every subset, every way to put queens on a chessboard so that none attacks another. If a problem asks only how many arrangements there are and that number is huge, count them with dynamic programming instead.

Explanation

You have three cards, numbered 1, 2 and 3. In how many orders can you lay them in a row?

To list them without missing one, put a card in the first position, then one of the cards left in the second position, then the last card in the third position. When the row is full, write it down. Then take back cards from the end until you reach a position that still has a card you haven't tried there. Put that card in, and fill the rest of the row again.

Fig. 1. Card 1 stays in the first position while both orders that start with it are written down. It leaves only when positions 2 and 3 have nothing left to try.

This gives 6 orders: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2 and 3 2 1. A card that is already in the row is never offered again. That is a check, and it is made when the card is put down, not when the row is full.

Now add a rule that can fail. Put 4 queens on a 4×4 chessboard so that no two of them attack each other. A queen attacks every square in its row, in its column and on both of its diagonals. Row 1 is the top row, and column 1 is on the left.

Fig. 2. A queen attacks its row, its column and both diagonals. Can you put 4 queens on the board so that none attacks another?

Try the obvious way first: in each row, put the queen on the first free square. Row 1 gets column 1, and row 2 gets column 3. Now row 3 has no free square. Columns 1 and 3 are below the two queens, and columns 2 and 4 are on the diagonals of the queen in row 2. Unlike a card, a queen can make the board impossible to finish, and you find out only a row later. Some earlier queen must move, but which one, and where to? To be sure, you have to try them all.

Two queens in one row attack each other, and there are 4 queens for 4 rows, so each row holds exactly one queen. The same goes for the columns. So a placement is an order of the columns 1 to 4, one column for each row, just like an order of four cards. List all 24 orders as with the cards, and check the diagonals only when the board is full.

Fig. 3. Both boards start with columns 1 and 2. Those two queens already attack each other, but checking only full boards builds both boards to the end.

This finds both placements. But half of the 24 orders are broken by their first two queens, as in Fig. 3. On a 12×12 board, checking only full boards means building 479,001,600 orders, which takes about 2.6 seconds.

Why finish a board that is already broken? Check each queen when you put it down. If its square is attacked, try the next square in the row. If every square in the row is attacked, don't go on. Take back the queen in the row above and move it to its next square.

On the example: after the queen in row 1, column 1, the square in column 2 of row 2 is rejected at once. Neither board in Fig. 3 is ever built, and no placement is lost: adding more queens never removes an attack, so a board with two queens attacking each other can never be finished. Every other choice is still tried.

This is backtracking: build the answer one choice at a time, check each choice as soon as it is made, and when you are stuck, go back to the last position that still has a choice left. Listing the cards was backtracking too, with the check "this card is not in the row yet".

Here is the search on the 4×4 board up to its first placement. In each row it tries the columns from left to right.

The board is empty. The search starts in row 1, column 1.

Row 1: column 1 is free, so the queen goes there.

Row 2: columns 1 and 2 are attacked, so the queen goes to column 3.

Row 3 has no free square, so the queen in row 2 is taken back from column 3.

Row 2: column 4 is the next square after column 3, and it is free, so the queen moves there.

Row 3: column 1 is attacked, so the queen goes to column 2.

Row 4 has no free square, so the queen in row 3 is taken back from column 2.

Row 3 has no free square after column 2, so the queen in row 2 is taken back from column 4.

Row 2 has no column left after column 4, so the queen in row 1 is taken back from column 1.

Row 1: column 2 is the next square after column 1, and it is free, so the queen moves there.

Row 2: columns 1, 2 and 3 are attacked, so the queen goes to column 4.

Row 3: column 1 is free, so the queen goes there.

Row 4: columns 1 and 2 are attacked, so the queen goes to column 3.

Every row has a queen: the first placement is 2 4 1 3. 8 queens were put down and 4 taken back.

1/14

Fig. 4. Backtracking on the 4×4 board up to its first placement. The dark blue square is the queen just put down and light blue squares in its row were attacked. A queen with a blue outline is being taken back, and its box turns red. The boxes beside the board list the column of the queen in each row.

The first placement is columns 2, 4, 1 and 3 in rows 1 to 4. The search put down 8 queens to find it and took back 4. Run on, it finds one more placement, columns 3, 1, 4 and 2, the mirror image of the first, and then stops. For the whole board it puts down 16 queens, while checking only full boards puts down 64. On a 12×12 board the gap is much wider: 856,188 queens against 1,302,061,344.

In Fig. 5 the choices of the whole run form a tree. The empty board is on the left, each column of circles to its right is one row, and each circle is one queen put down, branching into the choices tried after it.

Fig. 5. 16 queens in all. A cross means the next row has no free square.

Subsets

Which of the cards 1, 2 and 3 can you keep? Now you decide the cards one at a time, and each card has two choices: leave it or take it. The method is the same, and no choice can be wrong, so there is no check. Decide card 1, then card 2, then card 3, and write down the cards taken. Then take back the last choice and try the other one. Leaving comes first. The choices form a tree again, and each bottom end of it, a leaf, is one subset.

Fig. 6. Level 1 decides card 1, level 2 card 2, level 3 card 3. Edge 0 leaves the card, edge 1 takes it. The blue path takes card 1, leaves card 2 and takes card 3.

Implementation

On the board, a position is a row and a choice is a column. Rows and columns are numbered from 1, row 1 at the top, and n is the size of the board. The queen in row r stands in column c.

The number of rows comes from the input, so the program can't have one loop for each row. Instead a function fill(r) puts a queen in row r and calls itself for row r + 1, which is recursion. Going deeper is a call. Going back is a return.

The board is kept in arrays that all calls share. col[r] is the column of the queen in row r, used to print the placement. Three arrays mark what the queens already attack:

• usedCol[c] is true if column c has a queen.

• diag1[r + c]: on a diagonal going down to the left, every square has the same r + c, from 2 to $2n$.

• diag2[r - c + n]: on a diagonal going down to the right, every square has the same r - c, from 1 - n to n - 1. Adding n keeps the index between 1 and 2n - 1.

Fig. 7. Left: on a diagonal going down to the left, every square has the same r + c. Right: on a diagonal going down to the right, every square has the same r - c; adding 4 makes the numbers start at 1.

Local variables such as c belong to one call. The arrays don't: what a call writes into them is still there after it returns. So right after the recursive call returns, the program must clear the marks it set. That is the take-back step.

1. Initialise: no queen on the board; call fill(1).

2. Done?: if r > n, every row has a queen. Record the placement and return.

3. Try each choice: go through the columns c from 1 to n.

4. Check it: skip c if its column or one of its diagonals is marked.

5. Put it: set col[r] = c and mark the column and both diagonals.

6. Go deeper: call fill(r + 1).

7. Take it back: clear the three marks. The loop then tries the next column.

The program reads n and prints every placement as the columns of rows 1 to n, then the number of placements cnt. With firstOnly set to true it stops after the first placement (see below). For the 4×4 board the input is:

4

#include <iostream>
#include <vector>
using namespace std;

int n, cnt = 0;
bool firstOnly = false;   // set to true to stop at the first placement
vector<int> col;
vector<bool> usedCol, diag1, diag2;

void fill(int r) {
    // done? every row has a queen
    if (r > n) {
        cnt++;
        for (int i = 1; i <= n; i++) cout << col[i] << (i < n ? ' ' : '\n');
        return;
    }
    // try each choice: the columns of row r
    for (int c = 1; c <= n; c++) {
        // check it: skip an attacked square
        if (usedCol[c] || diag1[r + c] || diag2[r - c + n]) continue;
        // put it
        col[r] = c;
        usedCol[c] = diag1[r + c] = diag2[r - c + n] = true;
        // go deeper
        fill(r + 1);
        // take it back
        usedCol[c] = diag1[r + c] = diag2[r - c + n] = false;
        if (firstOnly && cnt > 0) return;   // only needed to stop at the first placement
    }
}

int main() {
    cin >> n;
    // initialise: no queen on the board
    col.assign(n + 1, 0);
    usedCol.assign(n + 1, false);
    diag1.assign(2 * n + 1, false);
    diag2.assign(2 * n + 1, false);
    fill(1);
    cout << cnt << '\n';
}

The first line it prints is 2 4 1 3, the placement found in Fig. 4.

Each check takes $O(1)$ time with the three arrays, and the search never puts down more queens than listing all $n!$ orders would, so the time is at most O(n \cdot n!) and the memory is $O(n)$. In practice the checks cut off far more: for n = 12 the search puts down 856,188 queens and runs in about 0.05 seconds.

Listing every answer costs at least one step per answer, and a common rule of thumb is about 10^8 simple steps per second. So all orders of $n$ items can be listed for n \le 10 (10! = 3{,}628{,}800), and all subsets for $n$ up to about 20–25 (2^{20} \approx 10^6). Above that, backtracking works only if the checks cut off most branches, as for queens up to about 12.

All orders

For the cards, a position is a spot in the row and a choice is a card. a[i] is the card in position i, and used[c] is true while card c is in the row. The check is used[c], and taking back is used[c] = false. Only a few lines change:

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> a;       // a[i] = the card in position i
vector<bool> used;   // used[c] = card c is in the row

void fill(int i) {
    // done? every position has a card
    if (i > n) {
        for (int j = 1; j <= n; j++) cout << a[j] << (j < n ? ' ' : '\n');
        return;
    }
    // try each choice: the cards
    for (int c = 1; c <= n; c++) {
        if (used[c]) continue;     // check it
        a[i] = c;                  // put it
        used[c] = true;
        fill(i + 1);               // go deeper
        used[c] = false;           // take it back
    }
}

int main() {
    cin >> n;
    // initialise: the row is empty
    a.assign(n + 1, 0);
    used.assign(n + 1, false);
    fill(1);
}

On input 3 it prints the 6 orders of Fig. 1, in increasing order.

Subsets

For subsets, choose(i) decides card i. It first leaves the card and goes deeper, then takes it, goes deeper again and takes it back. The cards taken so far are kept in a vector chosen:

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> chosen;  // the cards taken so far

void choose(int i) {
    // done? every card is decided
    if (i > n) {
        cout << '{';
        for (int j = 0; j < (int)chosen.size(); j++) cout << (j ? " " : "") << chosen[j];
        cout << "}\n";
        return;
    }
    choose(i + 1);         // leave card i
    chosen.push_back(i);   // take card i
    choose(i + 1);
    chosen.pop_back();     // take it back
}

int main() {
    cin >> n;
    choose(1);
}

On input 3 it prints {}, {3}, {2}, {2 3}, {1}, {1 3}, {1 2} and {1 2 3}, the leaves of Fig. 6 from top to bottom.

To take exactly $k$ cards, add two checks: take a card only while fewer than $k$ are taken, and leave it only if enough cards remain after it to reach $k$. For example, with cards 1 to 4 and k = 2, if cards 1 and 2 are both left, card 3 can't be left too: only card 4 would remain, and one card can't make 2.

Stop at the first placement

Some problems want one placement, and printing all of them is a wrong answer there: on input 4 the main program prints two. Set firstOnly to true. The line if (firstOnly && cnt > 0) return; then leaves every loop as soon as one placement is printed, so on input 4 the program prints 2 4 1 3 and then the count 1. A count of 0 means there is no placement.

Common mistakes

• Forgetting to take a choice back right after the recursive call, so the old marks stay and free squares or cards look taken. Clear the marks as soon as the call returns.

• Checking the column and only one diagonal, so queens that attack each other along the other diagonal pass the check. Mark and check diag2 too.

• Cutting off a branch that could still be finished, such as stopping as soon as a sum passes its target when negative numbers could still bring it back. A check may cut off a branch only if no later choice can repair it.

• Listing the answers one by one when only their number is asked and the number is huge. Count them with dynamic programming instead.

Similar techniques

Depth-first search walks a graph the way backtracking walks its tree of choices: deep first, back when stuck. But a graph search keeps its marks, so each vertex is entered once. Backtracking takes its marks back, so the same card or column is used again in other branches. Removing the marks in a graph search turns it into backtracking over all paths, which can take exponential time instead of O(n + m).

Bitmasks list all subsets of $n$ items as the numbers $0$ to 2^n - 1, with one loop and no recursion. But a loop can't skip a whole branch when an early choice is already wrong.

Dynamic programming answers "how many" or "what is the best" when many branches lead to the same remaining question, such as the same sum still to reach.

Meet in the middle handles subsets of up to about 40 items: list the subsets of each half separately, about 2 \cdot 2^{20} of them, and combine the two lists.

Breadth-first search is for problems that ask for the fewest moves from one state to another: it finds them without trying every sequence of moves.

Practice