come up with a set of rows that contain exactly one 1 for every column/constraint, we search recursively using backtracking. Each Node points to four other nodes as mentioned, as well as its ColumnNode. In the case of Dancing Links, for every column of the linked list, there is a special ColumnNode (which extends the normal Node) that contains identifying information about that particular column as well as the size of the column i.e. the last element will point to the first one. Thus, every node in such a list will be connected to 4 other nodes and the list will be circular i.e. The idea is to take the exact cover matrix and put it into a toroidal circular doubly-linked list. Now, Dancing Links is an efficient way of solving such a problem.
A set of rows that together have exactly one 1 for each column can be said to be the solution set of the exact cover problem. Every row will have a 1 in every column (constraint) that it satisfies, and a 0 otherwise.
Exact Cover And Dancing LinksĪn exact cover problem can be represented as a sparse matrix where the rows represent possibilities, and the columns represent constraints. I convert the Sudoku puzzle into an exact cover problem, solve that using the Dancing Links algorithm as described by Dr Donald Knuth, and then get the solution and map it onto the Grid. My class AlgorithmXSolver takes an unsolved Sudoku puzzle as an int (the Grid) and outputs the solved Sudoku puzzle. Algorithm X, Exact Cover Problem And Dancing Links Implementation I believe my Algorithm X implementation is one of the few ones in Java (at least, I couldn’t find much online).Īnyway, here goes. And thus an assigment that should have taken a week to do ended up swallowing the better part of a month as I struggled with understanding Knuth’s paper and then implementing a Solver in Java.
I decided I would take a shot at using his technique to write a Sudoku Solver in Java. I read that no less than Dr Donald Knuth had thought and written about this, and he had described an algorithm to solve a Sudoku puzzle – Algorithm X+Dancing Links. Our prof told us that for the search engine he would give us a bunch of guidelines and classes to start us off, but wouldn’t give us anything for the Sudoku problem – it was billed as the more ‘open ended’ and ‘challenging’ of the two.īeing a nerd, I decided that I had to do the Sudoku Solver, and started reading online about Sudoku solving. For my Algorithms 1 course in Fall 2013, the final project was a choice between building a web search engine and an NxN Sudoku solver.
0 kommentar(er)
