Abstract |
Sudoku is the simple looking puzzle game that is sweeping newspapers across the country. Although the grid puzzle game appears easy, some of the challenging puzzles require advanced solving techniques that rely on the candidate values for a particular arrangement of cells. We have coded a computer program, written in C++, to utilize several of these techniques in solving Sudoku puzzles. The program operates on a 2-dimentional array of classes, which contain the given or assigned values for each cell, as well as the candidates of possible numbers for these cells. With this structure the program can operate on and update the cell’s candidate values, allowing it to utilize the more advanced solving techniques such as ‘Linked Doubles’ and ‘Swordfish’. In addition to these solving techniques the program also contains a function that demonstrates a recursive backtracking solution. The recursive backtracking function tests possible candidates for a cell and continues to check values for subsequent cells until it either finds the solution or runs into unresolvable problems and backtracks to a previous cell to try another number. This solution can be slow for certain puzzles due to the number of branches that the function has to check, but we believe that using the traditional techniques on the puzzle first can greatly reduce the branches that this function has to check. Primary tests seem to confirm this, further testing and calculations should reveal how much it can be sped up by.
|
Computer with Power Adapter