# Solving hard Sudokus really quickly

With a computer, you can solve Sudoku puzzles much, much faster than with pencil and paper—even the hardest ones. That's the claim that we're going to investigate in this explainer.

This claim raises several basic questions. When do we call a Sudoku puzzle hard? How come computers can solve these hard puzzles so quickly? And why do we care about solving these hard Sudoku puzzles so quickly in the first place? Let's start with some (first) answers to these questions.

## Human strategies

Sudoku puzzles are mainly a form of entertainment for humans. Solving them can be seen as a form of mental gymnastics, where you repeatedly have to find one of various patterns that allow you to draw conclusions about the solution, until you have. Most Sudoku puzzles can be solved in this way, using different patterns, some more complicated than others. This process of solving Sudoku puzzles is enjoyable and feels satisfying for many people.

Sudoku puzzles are typically given a difficulty rating. This rating is based on how complicated the patterns are that you have to find in order to get to the solution. There is no unique way of assigning a difficulty score to a Sudoku puzzle. There are several difficulty ratings for Sudoku puzzles that are commonly used in the online community, and different publishers of Sudoku puzzle books use different difficulty rating methods. What these ratings all have in common is that they are based on how difficult it is for humans to find the different patterns.

The basic approach is easy to explain. For all the cells for which you don't know yet what the solution is, you keep track of the remaining possibilities. Typically, these possibilities are written with pencil as small digits. For any cell, you can remove all possible digits for which there is a cell in the same row, column or block that has this digit as a solution.

One of the easiest patterns is the following. If there is only one possibility left for some cell, you can conclude that this must be the solution for this cell. This is called a *naked single*. Here is an example: the red cell contains a naked single.

Example: naked single (row 6, column 9)

Another pattern is called a *hidden single*. This is when in some row, column or block there is only one cell remaining that contains some digit as a possibility. (And no cell in the row, column or block has this digit as a solution yet.) Then this digit must be the solution for this cell. Here is an example—the red cell is the only cell in the top row where a 5 can still occur.

Example: hidden single (row 1, column 8)

These are only two very simple examples of patterns. There are many more of them, and they can get quite complicated to spot.

## Using the advantages of computers

Computers can solve Sudoku puzzles very differently from humans. This is because computers are very good at doing several things that are hard for humans. One of these things is pattern matching. If you spell out what the patterns are that the computer has to look for, it can find these very efficiently, whereas humans have a harder time to find these patterns in a sea of digits.

Another thing that computers are very good at is keeping administration. When you run out of patterns to spot, and you can't draw any more conclusions about the solution, you can just try putting some digit somewhere—guessing. If this leads to a solution, great! If not, you just go back, and rule out the possibility that you tried. This is called *backtracking search*. In order to make this work, you have to keep track of what conclusions depend on what guesses, and in what order you did the guessing. You can also do this with pen and paper, but it's a lot of administration to keep, and computers are very good at this.

By just using the brute speed of, say, a laptop computer, even a simple backtracking search algorithm can solve the hardest Sudokus in a matter of minutes. It is relatively easy to improve this to a matter of seconds, by adding a few of the simplest patterns that humans use: naked singles and hidden singles. More intelligently designed algorithms can do even better: they can solve even the hardest Sudokus in a matter of milliseconds.

## Sudoku puzzles as a case study

You might ask why it is so important to solve Sudoku puzzles so quickly? It isn't, really. A big part of the appeal of Sudoku puzzles is the solving process, as a form of entertainment. And even if you only care about finding the solution, probably the basic backtracking algorithms (with a few extra tricks sprinkled in) are good enough for Sudoku puzzles.

Sudoku puzzles are simply a (small) showcase example to illustrate intelligently designed search algorithms that employ reasoning about the problem. For search problems 'in the wild', the search space is typically even much larger. Think of finding a charging strategy to ensure that your fleet of hundreds of warehouse robots do not run out power, with a limited number of charging stations, for example. The number of possible strategies here is astronomical.

For such larger search problems, it is important to design intelligent algorithms if you want to find a solution quickly. You can see this already when you go to larger Sudoku puzzles. For 16 × 16 or 25 × 25 Sudoku puzzles, the unsophisticated algorithms already take an enormous amount of time on the harder puzzles.