A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm

Dancing Links is a powerful algorithm that solves Exact Cover problems. These problems can lead to interesting algorithmic exercises such as the Pentominos problem, polyiamonds, tetrasticks, the N queens, traveling knight, and other chessboard derivatives. However, Exact Cover problems aren’t just theoretical mathematical puzzles though. They describe many real life problems: problems such as making hotel room assignments given a group that has a many specific room requests, and organizing simple flight schedules for airports. Dancing Links is a backtracking, depth-first algorithm that can find all possible solutions of the problem.