Super Efficient Sudoku Generation

While creating my very first web app, a Sudoku game: (https://sudoku.drismir.ca/). I hacked together a backtracking algorithm to generate the boards. For Sudoku, backtracking felt very brute-force-y so I promised I would find a more efficient way.

It turns out there is pretty much only one option for quicker board generation and that is the dancing links algorithm by Donald Knuth from the year 2000! He wrote a paper on it, but honestly the paper was so abstract I could not make much of it. The resource that carried me through the project was this writeup on how the 2007 Nintendo DS game Zedoku implemented dancing links. (The original website for the writeup has been lost to time so I had to use the wayback machine to access it 😬)

The Reduction Part of the Algorithm

Dancing links does not solve Sudoku specifically, instead it solves an absolute cover problem. That is, given a list of rows, find a selection of rows that have only one cell in every column.

For example, in the absolute cover problem below, there are two selections that solve the problem.

Solution 1

Solution 2

Therefore, to get dancing links to solve a sudoku board we must first devise a reduction algorithm that will convert the constraints of a sudoku board into an absolute cover problem. For exactly on how we might do this checkout the zendoku writeup above, it is a very good resource.

The TLDR; for the reduction is that we have a 729x324 table, where every row represents a single number being assigned into a single cell (Ie. row 0 represents placing a 1 into the top left cell). Every column represents a constraint (ie. row 1 must have a 5 in it).

We feed this 729x324 table into our implementation of the dancing links algorithm and it will return a list of rows where each constraint is satisfied exactly one. This means by definition that it is a valid sudoku board.

Once dancing links returns the list of rows, we are not finished yet, we need to convert each row back into it’s respective number assignment on the sudoku board.

The Dancing Links part of the Algorithm

The reduction is only half the battle of the algorithm. If you used only the above insights you would actually be implementing algorithm x, not dancing links. And for sudoku, you end up spending so much time searching through your massive 729x324 table, that it ends up being slower than the obvious backtracking algorithm.

I would know, because that is exactly what I did, and this was the result I got:

To finally make this a dancing links implementation you must represent the table with a doubly linked list, with column headers tracking the number of cells below. Note the pointers wrap around the edges of the board.

If you look at the cycle of four operations taken by dancing links you will be able to put together how we can use these pointers to completely avoid searching the table for populated cells.

As a single example on how dancing links optimizes our search for rows. In step 2 where we need to find a row that satisfies our selected column, dancing links allows us to instantly find the next available row instead of needing to check every index in that row. (Link to source code for selecting row)

It would be impossible to enumerate all the fiddly details of implementing dancing links (which is probably why knuth and the Zendoku writeup avoid doing it as well). If you would like to implement this algorithm for yourself work through some simple examples to understand the ideas behind the reduction, the run through the algorithm by hand to understand the huge time save dancing links gives.

How Fast is it?

Thankfully, after implementing dancing links I was able to beat backtracking (unlike my algorithm x implementation which was an epic fail).

Here is the performance of all three:

I also wanted to get a feel for what my algorithm was really doing, so I created a visualization of the 729x324 table and the links as they traverse toward a solution. Check this out:

Source code for this project is here: https://github.com/ArmanDris/dancing_links_sudoku