This post is part of a series where I explain how to build an augmented reality Sudoku solver. All of the image processing and computer vision is done from scratch. See the first post for a complete list of topics.

### How to play

Sudoku is a puzzle game played on a 9x9 grid. The grid is evenly divided into 3x3 sub-blocks. Each space in the grid is filled with a digit from 1 to 9. No column, row, or block can contain the same digit more than once. Puzzles start with a number of digits already filled in and can often have more than one solution.

 3 2 1 7 9 4 2 3 9 4 8 7 1 2 9 7 8 8 6 1 7 2 3 1 8 5 7 8 6 9 6
An example Sudoku puzzle.

When you play the game, a natural strategy is to jump around filling in digits where there can only be one answer. Easier puzzles can be solved with this method alone but harder puzzles force you to guess. Of course, a side effect of guessing means that sometimes you find out you’re wrong and are forced to backtrack. A very tedious process. If you have an army of evil minions to delegate such tasks too, then uhh…just do that. For the rest of us, we’ll have to settle for using a touch of math and code to much the same effect.

### Finding A Solution

Let’s say you hung a puzzle on a wall. Then you threw a dart at the puzzle, hitting a completely random open space. Using a little set theory, you can determine all of the possible digits that could fit into that space.

#### Set Theory Refresher

Set theory is the study of sets. A set is an unordered collection of objects. Basic set theory is usually covered in the study of discrete mathematics.

The union of two sets, denoted uu, is the set with all of the objects in each set. Consider the numbered sets A and B

A = {1,3,2}

B = {5,4,3}

Then the union of these two sets is

A uu B = {1,2,3,4,5}

The universal set is a set containing all of the possible objects that should be considered and is denoted U. If, for example, only digits 1-9 should be considered, then

U = {1,2,3,4,5,6,7,8,9}

The absolute complement of a set is a set with all of the objects in the universal set but are NOT in another set. The absolute complement is written as U \\\ A or A′ where A is an arbitrary set.

C = {2,4,6,8}

C′ = U \\\ C = {1,2,3,4,5,6,7,8,9} \\\ {2,4,6,8} = {1,3,5,7,9}

Let the sets of digits in the current column, row, and block be denoted C, R, and B respectively. Then all of the unavailable digits are the union of these sets.

N = C uu R uu B

Since N is the set containing all of the unavailable digits, the absolute complement has to be all of the available digits.

A = N′

Here’s an example using the puzzle from earlier. Assume the top-left corner is coordinate (1,1) and coordinates are ordered horizontally left-to-right and vertically top-to-bottom. Using the open space at (3,7), start by finding the digits that are unavailable in the same column, row, and block.

 Column 3 2 1 7 9 4 2 3 9 4 8 7 1 2 9 7 8 8 6 1 7 2 3 1 8 Row Block 5 7 8 6 9 6

C = {9,2,5}

R = {7,2,3,1,8}

B = {7,5,9}

Union these sets together to find all unavailable digits.

N = C uu R uu B = {9,2,5} uu {7,2,3,1,8} uu {7,5,9} = {1,2,3,5,7,8,9}

Finally, compute the complement to get the available digits.

A = N′ = U \\ N = {1,2,3,4,5,6,7,8,9} \\ {1,2,3,5,7,8,9} = {4,6}

With a set of available digits in hand, one of the digits is removed from the set and put into the open space. Then the process is repeated at another open space. If no more spaces are open, the puzzle has been solved! If an open space has no available digits, one of the previous guesses must be wrong. Which means going back and trying a different digit. This process is called a depth-first-search.

One question remains: does it matter how an open space is chosen? An optimal method would be to seek out the open spaces with a minimal number of available digits. Otherwise, many more paths have to be searched, as well as further, before being rejected and backtracking. But, the effort required to find such an open space might be greater than the time saved.

The simplest method, which works fine in practice, is to start at the top left and scan horizontally and then vertically. However, puzzles with many completely open blocks at the beginning will take a relatively long time to solve. Most puzzles are not like this but it can be a problem if the known digits are entered incorrectly (eg. character recognition fails because of poor lighting). In which case, a timeout might be necessary if a solution cannot be found within a reasonable amount of time.

### In Code Form

The state of the puzzle can be stored in a numbered 1D array of 9x9 elements where each value in the array represents its respective digit or zero if the space is empty. Using a 1D array to represent a 2D array of numbers is a pattern that will be very common later when working with images. A simple wrapper class makes querying the puzzle’s state trivial. Since this class isn’t used for an interactive game, there’s no reason to check if each Set() operation keeps the game’s state valid.

The STL has a std::set container and std::set_difference algorithm to fulfill the mathematical set needs. Unfortunately, they are too slow in this case1. Since the universal set is very small, at just 9 digits, and known ahead of time, a custom container can perform much better. The following implementation performs all insert, contains, and complement operations in O(1) time.

Finding the available digits is just a matter of querying the puzzle’s state for all of the unavailable digits and then calculating the complement.

Depth-first-search is easily performed using recursion. Start by selecting an open position. Find the available guesses. Then for each guess, apply it to the game’s state and repeat the process recursively.

The next open space is determined by just scanning ahead in left-to-right and top-to-bottom order.

That’s all there is to it! You might think with “Sudoku” in the title, this would be one of the biggest parts of the project. In fact, it’s the smallest and easiest! Next time I’ll start covering the augmented reality side by giving a crash course in image processing.

### Footnotes

1. I originally used std::set instead of rolling my own but the performance was terrible. Waiting several seconds to find and show a solution is an unacceptable experience. Solving the “World’s Hardest Sudoku Problem” takes ~6 seconds with std::set and ~0 seconds using the method listed here. (Linux, GCC 6.3.1, Intel Core i5-3550)