Backtracking Algorithms

Hello kind algorithmic adventurer. Welcome to a post where I spend way too much time playing with the backtracking technique. By the end of this post you’ll have a great idea of just how many use cases this algorithm has, and why you’d reach for this technique. Because I can run code on this page, I’ll leave the intense theory to Wikipedia or textbooks, and instead show a bunch of demos and share implementation notes. You need to know about this algorithm.

This technique comes up early in computer science courses, but when I looked it up in my handy copy of “Algorithms Fourth Edition, Robert Sedgewick & Kevin Wayne” – it was mentioned on page 921, the last page of the book. He writes that backtracking can be used to “avoid having to check all possible solutions”. Before we avoid all those extra possible solutions, how many more can there be?

Lets take the Sudoku puzzle shown here. It has 81 cells that take a number from 1-9. Maybe about 21 of them are locked in and thus can’t be changed – leaving 60 cells that you can change.

I had to remove 20 zeros above as it wouldn’t fit on the page. With some back of the napkin calculations we can figure out how long this might take a computer to figure out. Let’s say our computer can process 3 billion solutions per second.

We don’t have longer than the age of the universe to solve a Sudoku – so need a better way.

I mentioned before that I can run javascript on this page; so for your entertainment I’ve set up three Sudoku boards. Check out the rules of Sudoku for a refresher, and if you’re able to wait out the brute force solution send me a screenshot 🙃.

A brute force algorithm generates every single possible input for a problem, and then tests to see if it is valid. It is also sometimes called a generate and test algorithm.

It works like so:

1. Generate a possible solution.
2. Test to see if this solution is valid.
3. Celebrate if you have a valid solution, otherwise go back to step 1.

In code it can look like this – although I’ve intentionally laid it out in a way which becomes a backtracking algorithm easily.

function bruteforce(s) {
  if (s.accept()) return true;

  let s2 = s.first()
  while (s2 !== null) {
    if (bruteforce(s2)) return true;
    s2 = s2.next()
  }

  return false;
}

This bit of code takes s, and iterates through all the possible solutions with first, next and recursively calling on s2. If you pass bruteforce a valid solution, s.accept() will return true causing the search to stop. Shelve these methods in your memory, because we’ll dig into them in the context of backtracking.

Backtracking algorithms work by not pursuing solutions that are wrong – thus avoiding large amounts of work. Although that sounds like a forehead slapping statement, it is the secret sauce to their speed. To be able to use backtracking you must have a problem where you can reject a partial solution.

This partial solution can never be solved. The brute force algorithm has no logic to handle this, and will instead fill the rest of the space with attempts. You can see in the demo, the brute force solution spends a lot of time with the top half of the sudoku filled with 1’s.

The backtracking algorithm detects this case with one extra line of code:

function backtrack(s) {
  if (s.reject()) return false;
  if (s.accept()) return true;

  let s2 = s.first()
  while (s2 !== null) {
    if (backtrack(s2)) return true;
    s2 = s2.next()
  }

  return false;
}

The reject method looks at the partial state s, and informs the algorithm if there is any reason to keep searching. It’s an early exit and prevents deeper recursion if s can never be part of an accepted solution. If you accidentally reject a partial solution that could be part of a correct solution, then the algorithm will prune that whole search space and you won’t find the answers.

The brute force and backtracking algorithms shown above have a consistent interface. For a class to be solvable we need methods for:

• reject - returns true if we have an unsolvable partial state.
• accept - return true if the state is a valid solution.
• first - The first extension of the partial state.
• next - The next alternative extension of the partial state.

In TypeScript this becomes:

interface Solvable<Puzzle> {
  reject: () => boolean;
  accept: () => boolean;
  first: () => Puzzle | null;
  next: () => Puzzle | null;
}

The two tricky methods are first and next. The “first extension” and “alternative extension” instruct how we explore the solution space.

Imagine the solution space of a sudoku as a tree data structure. A node on this tree represents a value in a Sudoku cell. Each node has 9 possible children for the 1-9 integer in the next cell. Thus there are 9 possible nodes for the first (top left) cell in Sudoku. Then from each of those 9 possible nodes there are 9 possible children in the next cell. You can keep doing this until the board is full, leaving you a tree with a depth of 81 – the number of cells in a Sudoku board.

The first method returns the next cell with a 1 set. If we’re on the 81st cell – the Sudoku board is full and first returns null.

The next method increments the value in the cell. If the cell is at 9, next returns null signalling we’ve explored that sudoku cell completely.

Have a play, and then we can go line by line:

Lets describe what is going on line by line.

function backtrack(s) {

This declares a function backtrack. It takes s which is a partial solution to Sudoku in this case.

    if (s.reject()) return false;

In recursive functions it’s nice to check base cases up front. The first case is checking if we should reject the partial solution. If s is unsolvable then early return – preventing the futile search of an already wrong Sudoku. Returning here says to the calling function: you’re already wrong, I’d like you to try your next partial state.

    if (s.accept()) return true;

If the partial state s happens to be the answer of the Sudoku, then we return true. This will end the search. Returning true prevents the calling functions from continuing. This halts the search on the first accepted state the Sudoku encounters.

    let s2 = s.first()

We know the prior state s can be part of a solution (wasn’t rejected), and isn’t a solution (wasn’t accepted). It’s time to get the “first extension of the partial state” and assign it to s2. Recall that this assigns a pointer to the next cell with the first value “1” and assigns it to s2.

    while (s2 !== null) {

This loop ensures we loop over all the values 1-9 (with the next method), exiting if next returns a null – which happens when we’ve searched all 9 values that can be placed in s2.

        if (backtrack(s2)) return true;

The recursive magic! We pass our current partial solution into the backtrack function. It will either reject the partial solution letting us continue the loop out here. Or it will accept the partial solution – which is the only time it returns true. If it accepts the state then the search is over and we also return true. Finally it can explore every other option in the next cells, and if it doesn’t find a solution will eventually exhaust all options returning false.

        s2 = s2.next()

All cells ahead of this one didn’t have a solution (we’re after the recursion), so we increment to our next value.

    }

This closes out the while loop.

    return false;

We’ve explored every possible value in our cell, and with nothing more to do we return false.

}

The end of the function declaration and my fun attempt at literate programming.

An insight is that the backtracking happens completely with recursion. backtrack takes a partial state, makes sure it’s worth doing work on the partial state, then explores one small piece of the problem. The function backtracks by exiting, because the function that called it is working on the previous partial state – or cell for our Sudoku example.

If you imagine that the reject line is missing, you can see why the brute force starts by filling the Sudoku with 1’s. It calls first recursively over and over until the board is filled. Finally after the board is filled it starts calling next.

A backtracking algorithm will behave like a brute force algorithm if you implement reject to always return false, never culling any of the search space and checking every single cell.

We’re about to dive into the Sudoku class implementation. But before we show too much code I want to show two other backtracking problems. These implement the same Solvable interface and run through the exact same backtrack function.

Problem: Given an N by N sized chessboard. How can you place N queens such that no queen is attacking another. This demo places 8 queens on an 8 by 8 chessboard.

Problem: There isn’t one. We can just use the same exact interface in a fun way to draw a maze.

The backtracking algorithm randomly carves a path through the cells, marking them as visited. A dead end causes it to backtrack until it can resume carving. The algorithm finishes when every single cell has been visited resulting in a maze where any cell is reachable from any other cell.

We’ve talked about the algorithms and interface. The only thing that hasn’t been revealed is how the concrete implementation looks like in order to satisfy all the requirements.

So a prior version of me would try to conserve memory and try to solve this problem with mutation. Basically construct a Sudoku object and pass it into the algorithm. The methods first and next would mutate the properties on the object and everything would be awesome. Except then I’d realize that none of the backtracking works.

Why?… Because when your stack frame rejects and we backtrack into the calling function we find our same Sudoku instance with all its properties mutated. This is the classic bug that happens when you pass a reference into a function that mutates it, and suddenly it is mutated everywhere.

If we want backtracking to work we need exiting the function to return us to the prior partial state. We can return to the prior partial state if we make a new Sudoku board and copy the values. This is why we are assigning our new sudoku boards to s2 in the code samples. The copy in the function scope keeps track of the cell index and value within that function call.

Nothing teaches better than the code. I’ve omitted the accept and reject since they’re quite boring and long. Everything else is exactly as it’s running on the page.

type OptionalNumber = number | null;
type ImmutableBoard = OptionalNumber[][];
type MutableBoard = OptionalNumber[][];

class Sudoku implements Solvable<Sudoku> {

  // These are references
  private immutableBoard: ImmutableBoard;
  public mutableBoard: MutableBoard;

  // These point to a cell and the value of that cell
  private cellIdx: number;
  private cellVal: number;

  /**
   * Create a new Sudoku partial solution
   *
   * `immutableState` is the part of the Sudoku puzzle that cannot change.
   * `mutableBoard` is the part of the Sudoku puzzle we can update.
   *
   * `cellIdx` is an index to which cell this class is updating.
   * It's an int in the range [0, 80] that covers the 81 sudoku cells.
   *
   * `cellVal` is the current value in the `cellIdx`. Can take integer [1, 9].
   **/
  constructor(
    immutableState: ImmutableBoard,
    mutableBoard: MutableBoard,
    cellIdx: number | null,
    cellVal = 1
  ) {
    this.immutableBoard = immutableState;
    this.cellIdx = cellIdx === null ? -1 : cellIdx;
    this.cellVal = cellVal;
    this.mutableBoard = mutableBoard;

    if (this.cellIdx === -1) {
      return;
    }

    const [x, y] = this.getXY(this.cellIdx);
    this.mutableBoard[y][x] = this.cellVal;
  }

  getXY(cellToChange: number): [number, number] {
    const x = Math.floor(cellToChange / 9);
    const y = cellToChange % 9;
    return [x, y];
  }

  getCellValue(x: number, y: number): OptionalNumber {
    return this.immutableBoard[y][x] || this.mutableBoard[y][x];
  }

  reject(): boolean {
    // ... omitted for brevity ...
  }

  accept(): boolean {
    // ... omitted for brevity ...
  }

  // Returns the next extension of the partial solution.
  // For Sudoku that means a Sudoku class pointing at the next cell.
  // If we are in the last extension or 81st cell, return null.
  first(): Sudoku | null {
    // Skip immutable cells -- cells we cannot change.
    let nextCell = this.cellIdx + 1;
    while (nextCell <= 81) {
      const [x, y] = this.getXY(nextCell);
      if (this.immutableBoard[y][x] === null) {
        break;
      }
      nextCell += 1;
    }
    if (this.cellIdx === 80) {
      return null;
    }

    return new Sudoku(this.immutableBoard, this.mutableBoard, nextCell);
  }

  /**
   * Returns the next subproblem, and null if there aren't any more.
   * This means incrementing the value, unless the value is 9.
   * If cell value is 9, signal no more valid values with null.
   */
  next(): Sudoku | null {
    if (this.cellVal === 9) {
      const [x, y] = this.getXY(this.cellIdx);
      this.mutableBoard[y][x] = null;
      return null;
    }

    return new Sudoku(
      this.immutableBoard,
      this.mutableBoard,
      this.cellIdx,
      this.cellVal + 1
    );
  }
}

If you’ve gotten this far then thank you for reading! Now you have a better idea of the backtracking technique, and how to create data structures that backtrack.

If you’d like to play around with the NQueens or Maze demos – find the code here.

I don’t have a comments section or mailing list. Instead if you’d like to see what I do or have a correction / question – message me on my YouCodeThings twitter.

Some addition references used for this post:

• A great chapter on backtracking: https://jeffe.cs.illinois.edu/teaching/algorithms/book/02-backtracking.pdf

• Queen chess image from wikimedia: https://commons.wikimedia.org/wiki/Category:SVG_chess_pieces

• Time conversion used: http://extraconversion.com/time/seconds/seconds-to-attoseconds.html

• Made in TypeScript with Lit & P5.js.