-
Notifications
You must be signed in to change notification settings - Fork 0
Using Knuth's X algorithm (with DLX)
royalsflush/SudokuSolver
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
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 0
No packages published