phoenixsmaug / sudoku

Implementation of different Exact Cover Solvers and a benchmark with Sudokus.

Benchmark Exact Cover Solver with Sudoku

Julia implemenation of the classical three exact cover solver:

• Simple Depth first search

• Solve as a Linear Integer Program with HiGHS

• Knuth's Dancing Link Algorithm

Using benchmark() the performance of the three solvers at Sudoku can be tested. All three solvers have to solve the complete dataset of "hardest sudokus" here manually collected by the "The New Sudoku Players' Forum". It is not intended to compete with solvers specialized in Sudoku, but simply uses Sudoku as an example for Exact Cover problems. My results on a machine with an Intel Core i9-10980HK were:

Solver	Time
Dancing Links	4s
Integer Programming	100s
Depth first search	47s

(c) Mia Muessig