Combinatorial Optimization in JavaScript

If you remember from very early on in this article series we mentioned that designing algorithms requires both correctness and efficiency. For a certain set of problems, however, correctness is currently impossible.

The reason has to do with the search space to find the answers to these problems. Permutations, for example, expand at a factorial (n!) rate. Since modern computers can run millions of operations per second, we start to hit some difficulty when we are dealing with as little as 13 items to create permutations over.

In fact, this number expands so quickly that by the time we try something as seemingly practical as finding all permutations of a deck of cards (52!), we’re dealing with a search space so large that if you shuffled a deck every second since the universe began you still wouldn’t have seen all of the permutations!

So how do we deal with large search spaces when searching is impossible? Enter heuristics.

This article is part of the Data Structures and Algorithms Series following the course The Analysis of Algorithms. If you missed the previous article, check that out first as well as a copy of The Algorithm Design Manual.

By working backwards and using heuristics to approximate a correct solution, you can get close enough to a correct solution that is acceptable without having to run your computers for all of eternity. Before we get into that, let’s answer the previous article’s Daily Problem:

Answers to the previous Daily Problem

Let G = (V,E) be a directed weighted graph such that all the weights are positive. Let v and w be two vertices in G and k ≤ |V| be an integer. Design an algorithm to find the shortest path from v to w that contains exactly k edges. Note that the path need not be simple.

Keep track of all i hops to all i vertices. The shortest path for k edges is just the shortest path for k-1 edges plus some edge in our i. We can backtrack recursively from the end towards the beginning, appyling the lightest-weight edge as we head backwards towards our starting vertex.

This is the basis for how we will approach problems going forward.

Backtracking as a means of defining heuristics

Have you ever played Sudoku? Then you can understand backtracking! Backtracking, as we alluded to earlier, is the systematic way of going through all possible configurations of a search space, whether it is how they are arranged (permutations) or how they are divided (subsets). At each step in backtracking, we are trying to solve a portion of the total problem.

Let’s say we want to get from one end of the graph to the other; point A to point Z. And further we know that there are 5 different ways to get there. What backtracking will do is figure out all of the ways to get from A to Z by adding 1 more point to the solution. It will then ask “did we get to Z?” if it did, we can print out the solution, if not we have to see if we hit a dead end or if we can extend it further.

Since we’re going deeper into a list of possibilities leading from A to Z, it makes sense that we could implement backtracking with DFS. BFS also works since we are trying to find all possible solutions (i.e. going wide will accomplish the goal just as going deep will), but it takes up much more space since we’re guaranteeing to hit all of the dead ends rather than only going deep on the ones that get us closer from A to Z.

I was going to post some code that offers a way of explaining backtracking, but to be honest after looking over the algorithm it’s much easier to understand as a recipe list and then apply that to a specific problem. Therefore, let’s generalize backtracking into this recipe:

1. For a given solution A, if it’s a complete solution that gets us from A to Z, print it! If we haven’t found a solution yet, move on to step 2
2. Go one level deeper - given A, add one more step to your partial solution. This is like going to the next fork in the road.
3. Now go down each fork in the road and proceed to step 1 with each fork as the new A. So if we hit a fork in the road with 3 more streets to travel down, you’re re-running backtrack on A'1, A'2, and A'3. If we’ve done all of the exploring possible or hit a dead end, proceed to step 4.
4. Now that we’ve explored, we need to move out of where we’ve traveled - either to explore another road because our previous one has terminated, or to end the algorithm because we’ve explored all roads.

And that’s the basic gist of backtracking with DFS. From here we’ll look at a specific example that I mentioned earlier: Sudoku.

Backtracking by example: Sudoku

You’ve heard of Sudoku, right? You wouldn’t guess it from the name, but this French puzzle game is inherently combinatorial in nature. The object of the game is to take a 9×9 grid of blanks and fill it with the digits 1 to 9. The puzzle is completed when every row, column, and sector (3×3 subproblems corresponding to the nine sectors of a tic-tac-toe puzzle) contain the digits 1 through 9 with no deletions or repetition.

Backtracking is an excellent way to solve this problem because the game starts partially filled in. That is, Step 1 is already filled out for us (we have a given partial solution A) and we need to take incremental steps to get to a completed board. To begin, we need to answer 3 questions:

1. How do we set up this problem? Since we have a 2D board matrix, a 2D array will suit us well in JavaScript. And what do we put in these array values? The state of the board, which we hope to fill out completely by the end of the exercise.
2. What are the possibilities at each step to evaluate? The set of values that haven’t been taken yet in a given row, column, or sector.
3. How do we know when to backtrack? As soon as we are out of possibilities from Question 2 (i.e. we either have filled out the board or we have an invalid board).

With all of that in mind, we can now create a custom backtracking algorithm to solve a Sudoku board!

class SudokuSolver {
  const UNASSIGNED = 0;
  const DIMENSION = 9;
  const SECTOR = Math.sqrt(DIMENSION);

  constructor(board) {
    this.solve(board);
  }

  solve(board, row, col) {
    const [row, col] = this.findUnassignedLocation(row, col);

    // step 1 - print solution else find it
    if (row === -1) return this.processSolution(board);

    // step 2 - DFS; go one level deeper
    for (let number = 1; number <= DIMENSION; number++) {
      if (this.isValid(row, col, number)) {
        board[row][col] = number;

        // step 3 - if we've hit a valid spot to explore, go in!
        if (this.solve(board, row, col)) return true;

        board[row][col] = UNASSIGNED;
      }
    }

    // step 4 - we've done everything; time to backtrack!
    return false;
  }

  findUnassignedLocation(board, row, col) {
    let assigned = false;
    let currentLocation = [-1, -1];

    while (!assigned) {
      if (row === DIMENSION) {
        assigned = true;
      } else {
        if (board[row][col] === UNASSIGNED) {
          currentLocation = [row, col];
          assigned = true;
        } else {
          if (col < 8) {
            col++;
          } else {
            row++;
            col = 0;
          }
        }
      }
    }

    return currentLocation;
  }

  isValid(board, row, col, number) {
    return (
      this.isValidRow(board, row, number) &&
      this.isValidColumn(board, col, number) &&
      this.isValidSector(
        board,
        Math.floor(row / SECTOR) * SECTOR,
        Math.floor(col / SECTOR) * SECTOR,
        number
      )
    );
  }

  isValidRow(board, row, number) {
    for (var col = 0; col < DIMENSION; col++) {
      if (board[row][col] === number) return false;
    }

    return true;
  }

  isValidColumn(board, col, number) {
    for (var row = 0; row < DIMENSION; row++) {
      if (board[row][col] === number) return false;
    }

    return true;
  }

  isValidSector(board, row, col, number) {
    for (var currentRow = 0; currentRow < SECTOR; currentRow++) {
      for (var currentCol = 0; currentCol < SECTOR; currentCol++) {
        if (board[row + currentRow][col + currentCol] === number) return false;
      }
    }

    return true;
  }

  processSolution(board) {
    let boardStr = '';

    for (let i = 0; i < DIMENSION; i++) {
      for (let j = 0; j < DIMENSION; j++) {
        boardStr += grid[i][j];
      }

      boardStr += '\n';
    }

    console.log(boardStr);
  }
}

Alright, lots to unpack here! Let’s go through the four steps one-by-one and see how we’re achieving backtracking for our Sudoku solver:

1. Determine if the Sudoku board is solved

It may seem counterintuitive to check if you’ve solved the solution before you’ve actually gone and solved it, but we’re doing this first in the algorithm because we don’t want to go down any unnecessary roads. Remember, algorithms are as much about correctness as they are efficiency.

So before anything else, we need to see if we have anymore unassigned locations. That just means asking our program “are there any spots on the Sudoku board left to be filled?” If not, we process a solution (which just means printing out the items in our 2D array) otherwise we add our next step and dive in.

2. Loop through the numbers

Now that we have a cell, we need to see which number(s) fit into that cell. Since there are 9 numbers on a Sudoku board to work with, we iterate through all of those; and that’s where the DFS part comes in.

3. Dive into valid configurations

Let’s say we know that 3, 5, and 8 are all valid numbers that could go in our current cell. The DFS recursion basically says “let’s assume we fill out our board with the 3 here, will we be able to fill out the rest of our board?” And we try to fill out that board in the universe where 3 is in this cell.

4. Assign or backtrack

If we reach the end state, we’re done. If we reach an invalid board, then we know we have to backtrack through this whole recursive dive until we get back to where we set the 3. We then try setting the 5, and go through the whole thing again, filling out all of the remaining slots until we either reach the end state or an invalid one. Repeating with all of the valid candidates until there are no more.

And that’s it! Combinatorial optimization sounds like a mouthful when taken at face value. But in reality, it’s just doing a depth-first search on all possibilities until we find the right one (or ones) to solve our problem!

Onto the next Daily Problem

Now we can apply our skills with backtracking into the Daily Problem:

Multisets are allowed to have repeated elements. A multiset of _n_ items may thus have fewer than _n!_ distinct permutations. For example, {1,1,2,2} has only six different permutations: {1, 1, 2, 2}, {1, 2, 1, 2}, {1, 2, 2, 1}, {2, 1, 1, 2}, {2, 1, 2, 1}, and {2,2,1,1}. Design and implement an efficient algorithm for constructing all permutations of a multiset.

More problems to practice on

Implementing a heuristic for the graph bandwidth problem is the recommended way from the class to start diving into combinatorial search problems.

The Eight-Queens Problem is another classic combinatorial backtracking algorithm to implement if you’re looking for something slightly different.

Finally, the class-sponsored Homework 4 focuses purely on combinatorial search.

If you have an implementation to any of these, be sure to share it with me on Twitter!