Skip to content

royalsflush/SudokuSolver

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

3 Commits
 
 
 
 

Repository files navigation

Sudoku solver, using Knuth's X algorithm for the Exact Cover problem (using DLX)

What's been done:
1. Implement a sparse matrix using linked lists (2D lists)
2. Implement the DLX functions

Important note: it is not possible to add elements while using DLX (only on the 
complete matrix).
Important note 2: if you remove some rows/columns and readd only a few of them,
the matrix can be incorrect (that's a restriction I put to maintain the O(n)
complexity in the readd operation)

2 1/2. Make printing compatible with removal of columns
3. Test remove and insertion of lines and columns

Next steps:
4. Code the exact cover backtracking (using the lowest possible branching factor)
5. Test it with the wikipedia example
6. Apply it to sudoku (with wikipedia's 4 restrictions)

About

Using Knuth's X algorithm (with DLX)

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published