Sudoku as constraint problem

So, back to the topic that started this, solving a Sudoku in software while using heuristics that a human would apply. In this post I'll be looking at Sudoku as a Constraint Satisfaction Problem. In a later post I'd like to look at Sudoku as a Set Cover Problem and how this relates to Human Heuristics, but lets start viewing it as a constraint problem, which has much wider applications than cover problems.

The approach can be applied to a Sudoku of any size and with any shape for groups, but for explanation purposes, lets work with a 4 by 4 Sudoku with 2 by 2 groups. As a constraint problem, we have 16 variables, the 16 locations in the Sudoku. Each variable has four options for its value, 1, 2, 3 and 4.

Then there are constraints. No number can be repeated in each row, column or group. Last, but not least, the values that are already filled in are also constraints. Otherwise we'd be generating all Sudoku's instead of solving a specific one.

Now, a naïve approach would be to just try each possible value for each variable and then check whether all constraints are met. A computer could still solve the problem like this, but it is very inefficient and also far from the way a human would solve a Sudoku.

The human way is to try to use the solved variables and the constraints to determine the correct value for unsolved variables. This postpones the need for trying values as much as possible. A typical Sudoku that is not too difficult can be solved like this completely. For more difficult Sudoku's it's common to start keeping track of the possible values for each location using pencil marks.

This pencil marks notation is something we can easily convert into software and is the base for the representation. We keep track of all options that are still possible for each variable. Once a variable has only remaining option, it is solved and this option can be removed from other variables in the same column, row and group. Once all variables have only one reaming option, the Sudoku is solved.

For more difficult Sudoku's you might get to a point where all effects of the constraints on the initially filled in variables are spread, but you're not at a solution yet. At this point you'll have to pick a variable that still has multiple options and try each option. As a human, you would pick a variable with 2 options over a variable with 3 options. This is the most constrained variable heuristic, which also helps a computer to solve these problems more quickly.

For this post I've written a Sudoku solver treating the problem as a Constraint Satisfaction Problem. It reads 9 by 9 Sudoku's (with regular 3 by 3 groups) from a text file and writes the solved Sudoku's to another text file. The source is available at:

https://github.com/josvanouwerkerk/SudokuConstraint

No files with Sudoku puzzles are provided, but can be found for example at:

https://github.com/grantm/sudoku-exchange-puzzle-bank

For these specific files the offset to the actual Sudoku is 13 on each line, which is a parameter that needs to be passed to the solver. For example:

SudokuConstraint.exe medium.txt 13

For the medium set of puzzles from the source above, this solver solves about 200.000 Sudoku's per second on my machine. A bit more than I expected honestly.

The classic phone book

The classic example I use to explain data structures and running orders is getting a number from a phone book. For those who have never seen a phone book, it's just a, fairly big, collection of names in alphabetical order together with the phone number of that person.

A phone book is essentially a lookup from a name (key) to a phone number (value.) A very common operation in software. In many cases, software will just linearly iterate over the records until the key is hit to return the matching value. In Linq in C#:

records.First(r => r.Name == name).Phone

This is what I would call a sub-human approach. No human has ever looked through a phone book linearly from the start until coming across the target name. Even though the computer might still be faster using this approach, the approach itself is less efficient.

The human way to find a name in a phone book relies on the fact that the names are ordered. You'd open the phone book in some location to determine whether the target name is in front or behind that location. This reduces the relevant part of the phone book and you can continue doing this until you've found the correct location of the target name. This comes down to a binary search and this would be on par with the human approach.

Using a hash table is an even better approach for this problem and allows the time needed for the lookup to be independent from the size of the phone book. It's quite rare to have an algorithm with a running time that is not related to the size of the input.

Both indexing options (binary tree or hash) are very common in databases and are also generally available in programming languages. It's just a matter of realizing that it would be beneficial to use it. Again, even iterating linearly over a dataset the size of a typical phone book can be done with a computer quite fast.

So, back to running orders. The linear iterations option is denoted O(N), meaning that the time doubles every time the phone book doubles in size. The binary search is denoted O(log N), meaning that the time increments by the same amount every time the phone book doubles in size. The hash table option is O(1), meaning that time stays the same every time the phone book doubles in size.

Quite a difference, but I mainly find it interesting that the typical human behavior gravitates to the middle option, while it's quite common to gravitate to the slower option when implemented in software. Even though an even faster option is readily available.

Of course, for very thin phone books, the difference might be neglectable and then its easy to favor the cleaner notation of a linear search. And it takes time to create the data structure, so it's only useful when used often enough.

Introduction

Recently I've been working on a little logic solver hobby project. The idea is to apply generic* solvers on various problems like Sudoku or Kakuro puzzles, or the N-Queens problem.

While being generic, these solvers do use heuristics to arrive at a solution in a timely manner. These heuristics align with the way a human would solve for example a Sudoku puzzle. And there you have it, I want to dedicate this blog to explaining how these Human Heuristics can be applied to computer programs.

While looking for example puzzles in a computer friendly format, I've come across sources where a computer program would take more than 10 minutes to solve a Sudoku or Kakuro. The algorithms there don't incorporate these Human Heuristics, making them orders of magnitude slower. For reference, the same problems can easily be solved by a computer in less than 10 milliseconds.

And that's really the reason why I want to explain the use of Human Heuristics in computer programs. Because computers are so fast, they are often fast enough even when the problem is solved in a simple way. But the human equivalent to a computer program solving a Sudoku in 10 minutes, is just checking whether the sudoku is correct after trying every number for every location and taking years to solve a single Sudoku.

I hope to inspire other programmers with the way heuristics in computer programs align with the heuristics we use as humans. So when solving a problem, stop thinking about how you would solve the problem with a computer, but instead focus on translating the way you solve the problem as a human into a computer program.

*While you could of course make a solver specifically for a 9 by 9 Sudoku, my hobby project aims at using the same solver(s) for multiple problems. So not just Sudoku puzzles of any size, but also the N-Queens problem can be solved with exactly the same solver.