Optimi-Zi(n)g Sudoku-Solving

9 months ago

The Dancing-Links (DLX) algorithm is used to solve exact-cover problems, such as Sudoku, by modeling constraints and solutions in a sparse matrix.
Sudoku is converted into an exact-cover problem with 4 types of constraints: row, column, 3x3 block, and cell constraints, totaling 4*9*9 columns.
The DLX algorithm involves setting up a matrix, selecting pre-filled lines, and recursively solving constraints until all are met or a failure is encountered.
Optimizations in the Zig implementation included reducing memory allocations, using stack memory instead of heap, and leveraging compiler optimizations (`-Doptimize=ReleaseFast`).
Performance improvements were achieved by pre-allocating memory, skipping unnecessary line setups, and using Hotspot for performance analysis.
The final optimized solver achieved an average solving time of 0.061ms per puzzle, with potential for further improvements via multithreading.
The project demonstrated the effectiveness of DLX for Sudoku and hinted at its adaptability for other problems like N-Queens.

Hasty Briefsbeta