Solving a Sudoku puzzle of every size and form has always given me a sense of
happiness. I first wrote a Sudoku solver using naive backtracking (checking
every possibility) with my two other friends
Harsha back in 2007 as part of a
summer project, which involved developing a C program to solve a sudoku puzzle
and create a nice interface for it using
Fast forward a few years I came across a paper by Prof. Donald Knuth called the Dancing Links. This paper not only provides an algorithm to efficiently solve exact cover problems but also presents a neat little data structure to speed it up.
I have been meaning to try out Dancing Links to solve the Sudoku for some time but never got around to it. So, when I was playing around with Scala and wanted to write something up using it, I decided to go ahead and implement it.
What is implemented ?
- DLX data structure.
- Methods DLX data structure needs to support to facilitate AlgorithmX.
- Class to solve exact cover problems using DLX and AlgorithmX.
- Class to solve 9x9 sudoku problems using DLX and AlgorithmX.