written on Wednesday, November 30, 2016
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 Shreesha and 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 graphics.h in TurboC.
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.