README.md

FERI-SudokuDLX

Dancing Links (DLX) Sudoku solver at Artificial Intelligence (slo. Umetna Inteligenca).

Solves Sudoku using dancing links technique, an efficient implementation of Algorithm X, as suggested by Donald Knuth. Supports all NxN sizes where N is a perfect square (4x4, 9x9, 16x16 ...).

Thanks to KarlHajal/DLX-Sudoku-Solver for a high-performance C-like implementation that served as the most important reference for this implementation. Additional thanks to Jonathan Chu's Java Sudoku Solver and paper for another important reference.

Features

• Sudoku Solver using Dancing Links Algorithm
• Sudoku Grids NxN (N is perfect square)
  • Manual Input (non-validated - by design for DLX error testing)
  • Import Dotted String Format (size-validated only)
    • 53.2..4... (length: N*N)
  • Test Cases (9x9 and 16x16) (in-code on start)
  • Benchmark (build & search)

Setup

Dependencies:

• Qt

Resources

• KarlHajal/DLX-Sudoku-Solver (reference C++ implementation)
• Dancing Links, Donald E. Knuth, Stanford University paper
• A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm

Test Cases:

• Sudopedia: Test Cases
• Wikipedia: Sudoku solving algorithms
• Computing Magic Knight Tours: Sudoku