a little recursion help
I am currently making a program that solves sudokus and am running into a little difficulty. this is the solve function that's called from my main method. it is passed the 2D array containing the contents of the sudoku program. The program calls 3 other methods (CheckItRow, CheckItCol and CheckItSqu). These methods check the row, colum, and square (retrospectivly) to see if the number is already in use. If it works it then it assigns the value to the cell and continues on. If it reaches 9 and none fo the numbers work, it jumps back to the next one and changes it's number. It does this untill the puzzle is solved. DrawIt draws the table
public static boolean SolveIt (int x[] [])
{
int escape = 0;
for (int k = 0 ; k < 9 ; k++)//go thru each col
{
for (int j = 0 ; j < 9 ; j++)//go thru each row
{
if (x [k] [j] == 0)//if it's blank
{
DrawIt (x);//draw it for me
for (int i = 1 ; i < 10 ; i++)//go thru each potential number
{
System.out.println ("*" + i);
if (CheckItRow (i, j, x)) //if the number is not in the row....
{
if (CheckItCol (i, k, x))//if the number is not in the col...
{
if (CheckItSqu (i, k, j, x))//if the number is not in the square...
{
x [k] [j] = i;//assign our number to it
if (SolveIt (x))//and recurse forward!
{
return true;
}
}
}
}
}
return false;//if we get to 9 and it doesn't work, go back one
}
}
}
return false;
}
The problem I'm running into is once it hits cell 1,7 it's in a situation that it needs to go back to the begining and modify the first number(cell 0,0). when it hits cell 0,0 all it does is return false then stop. Is there some way to keep it going?
Thanks a load!
~ ArthanKhwelnul
PS. the whole code is availble at www.freewebs.com/sapphworks/solveit.htm
# 1
several things wrong with this code.
1) it is unreadable - code tags would help
2) it is unreadable - better names would help e.g. is k the index for row or for col or for the value that is stored in a slot? You could have used names like row, col, val, and saved yourself writing comments and saved me effort in reading. i and j are find values for a for loop but when you are nested that deep you need to use better names.
3) it is unreadable - too long. By the time you are nested 7 or eight levels deep it is hard to see what is going on. This is when you rewrite it to use subroutines (which will slow it down) to make clear what is going on.(which will speed development time, increase probability that code is correct, reduce debugging time and decrease maintainence effort.)
for example:
class Sudoku{
int[][] grid = new int[9][9];
void solve(){
Slot s = findEmptySlot(grid); // this routine is allowed to fail
if(!grid.emptySlot(s)){ // returned slot not empty means problem is solved
grid.output(); // if there are multiple solutions, each one will be output here, eventually.
} else { // put a valid value in the empty slot and try to solve remainder
for(int val = 1; val <10; val++){
if(grid.valid(s, val)){
grid.setSlot(s, val);
solve();
grid.setSlot(s, 0);
}
}
}
}
}
So written this way it more closely follows traditional recursive routine presentation. All recursive routines MUST stop recursing somehow. Generally this is the trivial case. So typically this is put right up front so you can see how it stops.
All your testing rows, cols and squares has been bundled into a single routine, valid. This is for presentation simplicity. Shoves all those details to another routine.
One thing that you were certainly missing in your routine was the setting the slots back to zero. You have to back out the things that you changed on your way in, otherwise you have permanently trashed your grid as you were attempting solution.
Yes, you can get your solution to work mostly the way you wrote it, without introducing classes like Slot, but there is merit in simplifying the code.
