An implementation of Donal Knuth's Algorithm X using Dancing Links, to create a sudoku solving algorithm.
Sudoku can be reduced to a search problem with states and actions, where a new state is generated by placing some number in a cell. The goal is to reach a state where all squares are covered whilst being within the rules of a sudoku. This can be described as an exact cover problem.
An exact cover problem is a type of constraint satisfaction problem, which can be represented by a 2D matrix of 1's and 0's, from which a subset of rows are selected, which represents the path taken in the search, such that placing corresponding 1's over 0's yields 1's (Hence cover).
e.g. [1,1,0,0] and [0,0,1,1] -> [1,1,1,1]
Here is a more in depth visualization of this: https://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm
Since sudoku is a type of exact cover problem, we can use Donald Knuth's Algorithm X, which is a very efficient type of recursive, backtracking, depth-first search.
The reason this algorithm is so efficient for this type of problem is due to the doubley linked list data structure and the 'dancing links'.
Below are the Wikipedia articles that give a more in depth explanation of these ideas
https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
https://en.wikipedia.org/wiki/Dancing_Links
This project was developed for the University of Bath's CM10310 Artificial Intelligence coursework.
The task was to create a sudoku solving algorithm as laid out in the sudoku.ipynb.
The solution can be found in sudoku.ipynb under Part 1
To test the solution, follow the instructions in the notebook by changing SKIP_TESTS to False in the cell below the submission and run it.
The tests use the data found in the data folder, in increasing difficulty.
I have also incuded the original readme file submitted with the coursework which outlines some of my design decisions.
Python 3 and Jupyter notebooks are required to use this project : https://jupyter.org/install
- Add GUI
- Allow inputting a custom sudoku
The original sudoku.ipynb Jupyter notebook without the solution was developed by the University of Bath for the CM10310 Artificial Intelligence coursework.