| rallveird
| Joined: 13 Jun 2005 | Posts: 31 | : | | Items |
|
Posted: Mon Jun 13, 2005 5:01 am Post subject: Solving example |
|
|
Just putting in a solving example for those who want to see how to solve sudokus by brute force. (Probably only for those people randomly dropping by this forum. Not ment for the members here who can do this by themselves This is an implementation in java but I'm sure everyone will understand it. I'm only posting the solving logic. The 2 function FindNextSpot() and FindPossibleNumbers() are the ones you need to code yourself.
If you want you can first do some logic solving to reduce the grid. And then you can put a lot of logic into FindNextSpot() and FindPossibleNumbers() to reduce the final brute force.
Chosing FindNextSpot() wisely you'll get a fast solving brute force even without using logic. The max number of iterations I've seen so far to solve a sudoku is less than 1000 using a medium smart FindNextSpot() function.
Code: |
protected boolean Solve() {
// Trying to keep the created variables to a minimium for speed
// It's recursive so the less we have the faster it will be
int[] coord; // The cell we will be investigating
int[] numbers; // The legal numbers for the cell
// Find the next empty cell
coord = FindNextSpot();
// No more cells, it must be a solution
if (coord[0] == -1) {
return true;
}
// Get the legal numbers for our new empty cell
numbers = FindPossibleNumbers(coord);
// And now we check all the numbers for the cell
for (int number=0;number<numbers.length;number++) {
// Set the cell to the number
grid[coord[X]][coord[Y]] = numbers[number];
// Counting iterations to find the solution
// Can be removed for faster solutiontime
solvecount++;
// Call it recursively to check next number
if (Solve()) {
// We found a solution. Recursively return true
return true;
}
}
// The number wasn't correct. Set it to 0 again
grid[coord[X]][coord[Y]] = 0;
// Couldn't find any solutions for the legal numbers for this cell
// in this recursion
return false;
}
|
So there you go. Now go out at create your own sudoku solver. |
|