Why attempt this?

If solving puzzles is fun, then solving puzzles that solve puzzles must be fun squared! For me, it was a few years ago that I was feeling bored after my shift at the bowling alley, and I wanted to finally conquer this puzzle that had haunted me for several years prior. This also ended up being a good move for my portfolio, as the final program ended up helping me land a software developer internship a few weeks later.

I'll admit, I had to do some research to find a solid algorithm for this problem, but I still implemented it myself, and I'd like to do a high level overview of how it was implemented, and why my initial solutions were much more convoluted than they seemed.

How to solve a software problem

Solving problems is fun for me. It's part of why I chose to work in software in the first place. I'm addicted to the high of finally producing a solution to a problem or puzzle that allows all of the pieces to fit together. But how should we go about solving problems, particularly in the field of software? This is typically the flow that takes place in my head when I'm trying to solve a software problem:

1. Break the problem into micro-problems
2. How would I as a person solve each of these micro-problems?
3. How can I make the computer emulate these solutions?

This is obviously very general, and makes the process sound much easier than it actually is. The first two steps are usually the easiest, but the third presents a puzzle on its own: a language barrier. People and computers do not speak the same language, and translating between the two can be a monumental task. This is part of what hung me up those years ago in my first attempts at creating a sudoku solver.

The unintuitive answer

The issue with this particular problem set is that the easiest solution is not at all how humans would naturally do it. Humans typically start in a sudoku square with the least unknowns, and through process of elimination, slowly jump around the puzzle, filling in guesses and/or answers until everything falls into place. For a computer, a particular searching algorithm happens to be a near perfect solution. The algorithm in question is called a backtracking algorithm. This is where the computer brute forces solutions until it finds the right one. The way that it does this is not random, nor is it a blind sequential guess, but rather a depth-first search. This means that the computer starts at the first unknown, and starts to guess. Below is a very basic implementation in C of how this algorithm works. This does not include checking the validity of the puzzle, or loading the puzzle into memory.

// Variables
int length = 9 * 9;    // 81 cells in a sudoku puzzle
int cell[length];      // This is where the puzzle lives in memory
int index = 0;         // This is our cell counter

// Populate the puzzle. Each cell should = 0
populate_puzzle(cell);

// Main solve loop
while (index < length) {
  // 1. Brute force guess
  cell[index]++;

  // 2. Check if the puzzle is still valid
  int valid = check_puzzle_is_valid(cell);

  // 3. If this number works, go to the next cell
  if (valid) {
    index++;
    continue;
  }

  // 4. If we're in an invalid state, we need to reset this cell, and go back.
  // This is the 'backtracking' part of the algorithm
  else {
    cell[index] = 0;
    index--;
  }
}

Let's talk about each of these parts

1. By incrementing the cell's value by one, we're guessing that in the final puzzle, this cell will have this value.
2. We at this point need to check if the puzzle is in a valid state. This means making sure each row, column, and square have no duplicate numbers.
3. If the puzzle is still valid, we will continue on with the assumption that we're on the right track. We will go to the next cell, and continue this process.
4. Inevitably, we will end up with a puzzle in an invalid state. This means we need to backtrack, and try something else.

Isn't this super slow?

Yes.

Well, for you and me it would be, but for a computer, this is nothing. I initially thought, "well, bruteforcing 81 cells with 9 different possibilities each would probably take a few thousand years to complete." And that would be correct, except for we're not guessing every single cell (there's already some filled in), and we're not just blindly guessing, there's a method to the madness.

It should be pointed out that there are certain puzzles (think with unknowns at the beginning each equaling 9,8,7,6,etc) that will take longer because the algorithm won't get to those higher numbers until it has exhausted all the possibilities before it. So this is not the fastest solution. But for every single puzzle I pulled off the internet and plugged into my program, the algorithm had no issues. For every hard puzzle I gave it, my program finished in ~5 milliseconds for harder puzzles. I do, however, run a decently hefty desktop, so I pulled this onto a t2.small EC2 instance, where I was seeing closer to ~8 milliseconds on harder puzzles.

My intuition (and probably yours too) told me that this solution would be incredibly slow, when in fact, it is very fast, and much easier to implement than to emulate how a human would do it.

Intuition sucks (sometimes)

Anyone who has taken a rudimentary psychology / logic class knows that intuition can be faulty. Sometimes the solutions that seem the craziest might just be the best.

Like I mentioned at the beginning of this article, I had years prior to completing this task tried to do exactly that to no avail. I was trying to write an algorithm that solved puzzles the way humans do. In fact, one of my mentors in the field, Joe DePung, told me that's exactly how he once wrote a sudoku solver for a job interview. When I attempted this, I did not succeed. It was only after trying something I thought was crazy, that I finally conquered the challenge.