Backtracking

Written by André Ryser. Translated by André Ryser.

Contents

Problem
Algorithm
Implementation
Runtime analysis

Backtracking is an algorithmic design strategy that, in contrast to the brute-force strategy, in which all possibilities are blindly tried out, the current partial solution is gradually expanded until a solution for the entire problem is found. When we can’t find any further expansion possibilities, i. e. we ended up in a dead-end street, we reverse past steps until we find a variant that has not yet been considered. This way we are guaranteed to find a solution, if one exists, or we know for sure that there is no solution. This procedure is also known as the trial-and-error principle. You may ask what the advantage over a brute-force strategy (where we systematically try out all the possibilities) is? By gradually expanding the solution, we reduce the number of possibilities that we have to test, which as we will see in the next example, can make a big difference.

Backtracking should only be considered if no DP or Greedy solution can been found beforehand, as the runtime is exponential in most cases. Often, in the worst case scenario, all subsets (two powers of N, $2^N$ ) or all sequences (factorial of N, $N!$ ) must be examined for an input of N elements. Backtracking is only possible if the input data is small, i. e. $n \leq 20$ .

Problem

A classic backtracking problem is the queens problem. At the same time you try to position all queens on the chessboard in such a way that they don’t threaten each other. We are interested in chess board positions where there is at most one queen in each row, column and diagonal. We now want to know how many such positions there are when the chessboard has $n\times n$ fields.

A possible solution to the queens problem.

Algorithm

The simple solution to this problem would be to go through all the possibilities to place the n queens on n rows. We can already be a bit smarter and not just place the queens wildly on the chessboard, but exactly one per column. Then we have n queens and for each lady there are n squares where we can place them, that means we have a running time of $n^n$ , which is already very big for $n=8$ ( $8^8 ~= 17$ million).

Backtracking helps us find a faster solution. By placing the queens one after the other and taking a step back as soon as two queens threaten each other, we can omit the check of many combinations from the previous solution.

We used the following algorithm: 1.) Set the first queen on the field at the top left. 2.) Go to the next column 3.) Find the next valid position for a lady in this column. If one exists, go to step 6. 4.) There is no valid placement for this lady, go back to the previous column. 5.) Go to step 3 6.) Place the queen on the first valid position. 7.) If it was the last queen we terminate, otherwise go to step 2.

After we have placed the queen in the first column, we try each positions in the second column one after another. For the first two positions (a) and (b) we immediately have an invalid position. Only on the third position do we find a valid possibility in the first two columns and start again on the first position of the third column (c).

Implementation

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

int n;
vector<int> board;

/* Print the current board, 1 indicates a queen */
void printBoard() {
  for(int i = 0; i < n; i++) {
    for(int k = 0; k < n; k++) {
      cout << ((k == board[i]) ? 1 : 0);
    }
    cout << "\n";
  }
}

/* check for every already placed queen if she can attack us */
bool canPlaceQueen(int queen, int row) {
  for(int k = 0; k < queen-1; k++) {
    if(board[k] == row || (abs(board[k] - row) == abs(k - (queen-1)))) // same row or diagonale
      return false;
  }
  return true;
}

void PlaceQueen(int queen) {
  for(int row = 0; row < n; row++) {
    if(canPlaceQueen(queen, row)) { // Check if the queen can be placed in this row
      board[queen-1] = row; // place the queen in this row
      if(queen == n) { // we sucessfully placed the last queen
        cout << "SUCESS: board variable cotains the solution\n";
        printBoard();
      } else {
        PlaceQueen(queen+1);
      }
    }
  }
}


int main() {
  cin >> n;

  board.resize(n);
  PlaceQueen(1); // Start with the first Queen in Row 0
}

To check if two queen are on the same diagonal we use the expression abs (Y1 - Y2) == abs (X1 - X2))

Runtime analysis

As we will soon see, the algorithm runs in $O(n! \cdot n^2)$ , instead of $O(n^n)$ with the brute-force solution. For example, for $n=8$ we only need ~40’000 steps instead of the ~17 million. Why is this solution so much faster than the systematic testing with brute force? Backtracking has the following two advantages:

Incremental structure: The possibilities are not constructed out of thin air, but instead are a minimal modification of the previous version. These modifications can also be reversed quickly if we run into a dead end.
Pruning: Entire classes of invalid positions can be omitted. In our example, for example we skip all possibilities in one step where both queens are on the first line in the first two columns.

To calculate the running time we proceed as follows. The queen in the first column can be placed on $n$ lines. For the queen in the second column we now only have $n-1$ possibilities, after all she can’t be on the same line as the first lady. So there are $n \cdot (n-1)$ possibilities to place the first two queens. For the third queen there are $n-2$ possibilities because now already 2 lines are assigned when we place the third queen. We do this for all $n$ queens and we get $n \cdot (n-1) \cdot (n-2)\cdots 2 \cdot 1 = n!$ possibilities. For every possibility we need $O (n^2)$ to find out if two queens are threatening each other. The runtime of the algorithm is thus $O(n! \cdot n^2)$ .