course-web-page-Fall-2021

Repository for the Fall 2021 course web page

View the Project on GitHub IUDataStructuresCourse/course-web-page-Fall-2021

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.

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

800 000 000
003 600 000
070 090 200

050 007 000
000 045 700
000 100 030

001 000 068
008 500 010
090 000 400

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.

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

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:

812 753 649
943 682 175
675 491 283

154 237 896
369 845 721
287 169 534

521 974 368
438 526 917
796 318 452