How computers solve Sudokus

Author: Ronald de Haan <me@ronalddehaan.eu>
First published: Sep 27, 2023. Last updated: Jan 30, 2024.
 

Surely you have seen how computers' sophisticated ability to extract patterns from large amounts of data has recently been heavily featured in the media and popular culture. This is very useful for some applications, but it is certainly not a cure-all, nor does it cover all intelligent types of computation. There are also many other intelligently designed algorithms that can be classified under the umbrella term Artificial Intelligence. This explainer is about one type of such intelligent algorithms.

The algorithms that we will see solve search problems in an ingenous way. One can think about them as reasoning about the problem, learning from this reasoning, and using the learned information to find a solution. We will explain how this works with the example of Sudoku puzzles.

Sudoku

For those that have never seen a Sudoku puzzle, it a type of puzzle where you have to complete a 9 × 9 grid, filling each cell with the digits 1 to 9 in such a way that (i) each row contains all nine different digits, (ii) each column contains all nine different digits, and (iii) each of the nine 3 × 3 subgrids (called blocks) contains all nine different digits. In the past few decades, these puzzles have grown enormously popular. You can very likely find them on the back pages of your local newspaper. There is an example of a Sudoku puzzle below.

Sudoku puzzles are a neat and clean example of a search problem. There is a clearly defined solution, and the task is simply to find it. This is not necessarily an easy task, because there are many possible solutions. In computer science terminology, we say that the search space is large. You can compare it to finding a needle in a haystack.

There are Sudoku puzzles in all kinds of difficulty levels. For the hardest ones, it can take humans hours (or more) to solve them. Computers can solve even these hardest puzzles very quickly, in a matter of milliseconds. They do so by combining their speed in carrying out calculations with intelligent algorithms.

A sneak preview

In this explainer, you will get an insight into how this works. I will explain several algorithms that computers can use for solving Sudoku puzzles, starting with a simple algorithm and moving to more intelligently designed algorithms. The latter algorithms are based on encoding Sudoku puzzles into a logic language, and using algorithms to solve the so-called satisfiability (or SAT) problem for this language. I will explain how this logic language works, and illustrate the basic working of state-of-the-art SAT solving algorithms.

I will also give you (interactive) demonstrations that illustrate how the various algorithms for solving Sudoku puzzles work. As a quick preview, here is one such demonstration. Click on "Run!" to see a (slow motion) visualization of how one of the algorithms solves the Sudoku puzzle below.

(Note: This explainer is best viewed on a computer with a modern browser—otherwise the demonstrations might not work properly.)

Ready?

Are you ready to dive in? Then let's get started ⇒ with the explainer!

(If you would rather get an overview of the different parts of the explainer first, then have a look at the table of contents.)