Valid board input is structured by listing each cell's value in order (left-to-right then top-to-bottom). The console interface requires that the user inputs the unsolved Sudoku board's data in a particular way. This class is used in BruteForceSearch to represent positions in the Sudoku board. This class is responsible for implementing the depth-first, brute-force search to solve the given Sudoku puzzle. This class is used to construct the toroidal doubly-linked list in DancingLinks. This class is used to keep track of each column of Nodes in DancingLinks. This class is responsible for creating and using the Dancing Links structure to solve the given Sudoku puzzle. In order to use the values, each class uses a static import of Constants. This final class is responsible for storing constants related to Sudoku puzzles. This class is responsible for the simple console interface that the user interacts with. I would highly suggest reading Knuth's paper on the approach. The Dancing Links technique relies on the behavior of recursive backtracking and toroidal doubly-linked lists, particularly in their ability to efficiently remove and restore nodes to their original positions in their respective lists.
Why Dancing Links (Toroidal Doubly-Linked Lists)?īy generalizing a 9x9 Sudoku puzzle as an Exact Cover problem, we can solve Sudoku puzzles incredibly efficiently by implementing the Dancing Links approach to Donald Knuth's Algorithm X. The user is given the option to solve the puzzle through a brute-force search or through a Dancing Links implementation. This program implements a simple console interface that allows the user to enter and solve 9x9 Sudoku puzzles.
0 kommentar(er)
