Optimi-Zi(n)g Sudoku-Solving

Optimi-Zi(n)g Sudoku-Solving

26 July 2025 , in Olivier's log

One of the first program that I wrote in Zig (in September 2023) was a Sudoku-Solver, implementing the dancing-links (DLX) algorithm. I decided to revisit this program recently to experiment with benchmarking and try to increase its speed.

Dancing-Links (DLX) algorithm applied to sudoku

The Dancing-Links algorithm is an efficient backtracking algorithm to solve "exact-cover" problems, by using a matrix of 0 and 1s.

Dancing Links on Wikipedia

In an exact-cover problem, there is a bunch of constraints (modelled as columns of a matrix) and many partial solutions (modelled as lines of a matrix). The goal is to pick some solutions, so that all constraints are met exactly once. In the matrix-modelisation a 1 in a cell means that this partial solution meets the given constraint. Solving the exact-cover problem transposes to selecting rows, so that each column as exactly one 1 in it.

To convert a sudoku to an exact-cover problem, we generate 4*9*9 columns to represent the following constraints:

a given number must appear exactly once in each sudoku-row (9*9 constraints)

a given number must appear exactly once in each sudoku-column (9*9 constraints)

... continue reading