Lecture: Backtracking

Backtracking is exhaustive search (like depth-first-search) with pruning. It is applicable anytime a solution to the problem can be broken into partial solutions, and there is a way to prune partial solutions that can’t be extended to a full solution.

The general recipe for backtracking is to write a recursive function of the following form.

solve(partialSolution) =
  if prune(partialSolution) 
    return null
  if accept(partialSolution)
    return partialSolution
  else
    for every way to extend partialSolution to partialSolution2:
      partialSolution3 = solve(partialSolution2)
      if partialSolution3 != null
        return partialSolution3
    return null

Example: Sudoku (world’s hardest by the mathematician Arto Inkala)

For each square, we record the set of all available numbers that are still valid choices, a technique called pencil marks.

We can prune a board if there is a square that no longer has any valid choices.

static boolean prune(Set<Integer>[][] PM, int m, int n) {
    for (int i = 0; i != m; ++i)
        for (int j = 0; j != n; ++j)
            if (PM[i][j].isEmpty())
                return true;
    return false;
}

We succeed, and accept a board, if all the squares have been filled in with non-zero numbers.

static boolean accept(int[][] board, int m, int n) {
    for (int i = 0; i != m; ++i) {
        for (int j = 0; j != n; ++j) {
            if (board[i][j] == 0)
                return false;
        }
    }
    return true;
}

If there are still choices to be made, the question is which square to fill-in next.

Of course, it should be a square that has not yet been filled-in, that is, a square with a 0.

We can speed up the search by using a most-constrained-first strategy. In this setting, a square is most-constrained if it has the fewest options left, i.e., the smallest pencil-marks set. The idea is that we better deal with the most-constrained square now because if instead we make other choices, the most-constrained square may become unsolvable.

static Coord
most_constrained(int[][] board, Set<Integer>[][] PM, int m, int n)
{
    int fewest_marks = Integer.MAX_VALUE;
    Coord best = null;
    for (int i = 0; i != m; ++i)
        for (int j = 0; j != n; ++j) {
            if (board[i][j] == 0 && PM[i][j].size() < fewest_marks) {
                fewest_marks = PM[i][j].size();
                best = new Coord(i,j);
            }

        }
    return best;
}

With the identification of the most-constrained square, we recursively investigate all the choices for that square. For each choice, we must update the pencil marks accordingly.

static void
update_marks(Set<Integer>[][] PM, int i, int j, int k, int m, int n)
{
    for (int ii = 0; ii != m; ++ii) // same column
        if (ii != i)
            PM[ii][j].remove(k);
    for (int jj = 0; jj != n; ++jj) // same row
        if (jj != j)
            PM[i][jj].remove(k);
    int a = i / 3;
    int b = j / 3;
    for (int ii = a * 3; ii != (a+1)*3; ++ii) // same 3x3 region
        for (int jj = b * 3; jj != (b+1)*3; ++jj) {
            if (! (i == ii && j == jj))
                PM[ii][jj].remove(k);
        }
}

We must make sure to use copies of the current board and pencil marks so that the different choices don’t stomp on eachother.

Putting this altogether, here’s a backtracking algorithm for Sudoku.

public static int[][] 
solve(int[][] board, Set<Integer>[][] PM, int m, int n) {
    if (prune(PM, m, n))
        return null;
    else if (accept(board, m, n))
        return board;
    else {
        Coord coord = most_constrained(board, PM, m, n);
        int i = coord.i, j = coord.j;
        for (int k : PM[i][j]) {
            int[][] new_board = copy(board, m, n);
            Set<Integer>[][] new_PM = copy_marks(PM, m, n);
            new_board[i][j] = k;
            update_marks(new_PM, i, j, k, m, n);
            int[][] result = solve(new_board, new_PM, m, n);
            if (result != null)
                return result;
        }
        return null;
    }
}

The solution generated in under a second for world’s hardest Sudoku puzzle is: