![]() Implementing the DancingLinks approach in Java The diagram that is shown in most of these other articles gives a great visual representation of the nodes linking and unlinking. Check out Knuth’s paper or any of the other articles linked below. Many other articles have been written about how the Dancing Links algorithm works, so I won’t attempt to explain this approach in any more detail. The part that makes this approach interesting is that as a cell is covered/removed, the adjacent cell links are updated to point to each other which unlinks the cell in the middle, but the unlinked cell still keeps it’s own links to the adjacent cells to the cell and allows it to easily be inserted back into the linked matrix when the algorithm backtracks to find other solutions. This approach is what Knuth calls ‘Dancing Links’ as cells are covered and uncovered. Knuth’s paper here observes that by removing (covering) and replacing (uncovering) links to adjacent cells in this matrix is a simple approach to remove rows from the matrix as they are considered as part of the solution and then insert them back into the matrix if a dead end is reached and alternative solutions need to be considered. This means for each row, there are only 4 cells out of the 324 that need to be tracked in the matrix – the matrix is mostly empty even though a complete grid of 324×729 would be a fairly large table of cells. The rest of the cells are not relevant and are omitted. ![]() This matrix for Exact Cover problems can be represented as a ‘sparse matrix’ where only the cells for each row that correspond to meeting a constraint need to be tracked. An Exact Cover solution is when a subset of the 729 rows is selected that satisfied all of the 324 constraint columns. … possible candidate values for the cells.įor 4 constraints applied to every cell in the 9×9 grid, there are 9 rows x 9 columns x 4 constrains = 324Ī grid of 729 candidate solution rows by 324 constraint columns can be constructed that represents the entire puzzle. Values 1 through 9 must exist only once in each squareĪ square (or region) is a 3×3 square – in a 9×9 grid there are 9 total squares, 3 across and 3 down.įor a 9×9 grid using numbers 1 through 9, there are: 9 rows x 9 columns x 9 (values 1 through 9) = 729.Values 1 through 9 must exist only once in each column.Values 1 through 9 must exist only once in each row.The 4 constraints that must be met for every cell are: There can be more than one solution, although a ‘proper’ Sudoku puzzle is defined as one for which there is only a single, unique solution. When a subset of possible candidate values are selected from the set of all possible candidate values that exactly meet all of the constraints once with no unmet constraints, this subset represents a valid solution. a finite set of all possible candidate values.a finite set of constraints that must be met for a complete solution.a set of constraints that define the rules of the puzzle.Instead, as an Exact Cover problem, any Sudoku puzzle can be defined as: As a casual player of these puzzles, this is how you would normally play, but it’s not the most efficient approach mathematically. The regular puzzle solving approach to solving a Sudoku puzzle is to look at it in terms of the 9×9 grid with some given clues already placed and then try to fill the blanks following the rules of the game, cross-checking that your solution is valid. Although I did end up with a partially working app that could find solutions to some puzzles using a brute force approach with backtracking (on github here), what I learned about Sudoku puzzles is that they can easily be solved if addressed as an Exact Cover problem. The point of the article was to illustrate that (in most if not all cases) if you don’t understand a problem, you’re going to struggle to find an appropriate solution. Several months back, I wrote a post about writing code to solve Sudoku puzzles.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |