|
View previous topic :: View next topic |
Author |
Message |
| drowne
| Joined: 02 Jun 2009 | Posts: 1 | : | Location: Italy | Items |
|
Posted: Tue Jun 02, 2009 10:24 am Post subject: [backtrack] I need some help with my algorithm |
|
|
I'm sorry to bother you, but I can't figure out why my backtrack algorithm is not working properly...
Code: | private boolean solveSudoku(int i, int j, int[] p) {
// limits
if (i == 9) {
i = 0;
if (++j == 9)
return true;
}
// if cell is not empty, jump over
if (getTile(i, j) != 0) {
return solveSudoku(i+1, j, getActualPuzzle());
} else {
// if this is the first cell to fill, save the coords
if(first) {
first=false;
fx = i;
fy = j;
}
}
for(int x=1; x <= 9; x++) {
if(setTileIfValid(i, j, x)) {
// Log.d("SUDOKU: ", "set["+i+"]["+j+"] at value: "+x);
if(solveSudoku(i+1, j, getActualPuzzle())) {
return true;
}
}
}
// backtrack
Log.d("SUDOKU: ", "***************** BACKTRACK *******************");
backtrack++;
setTile(i, j, 0);
Log.d("SUDOKU: ", "*** setTile "+i+" "+j+" a 0 ***");
if(i==fx && j==fy && !is_Solved()) {
int value = getTile(fx, fy);
if(setTileIfValid(fx, fy, value++)) {
first=true;
solveSudoku(fx, fy, getActualPuzzle());
}
}
return false;
} |
Can you help me please? |
|
Back to top |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Tue Jun 02, 2009 6:51 pm Post subject: |
|
|
Assuming the use of two seperated arrays, one with the sudoku clues (Example: Sudoku[row][col]) and a second one for the solving progress (Example: Solution[row][col]) starting as a copy of Sudoku[row][col] and who will eventually hold the solution, and assuming that changes only occur in the second array, this is how it might work...
Code: | private boolean solveSudoku(int i, int j, int[] p)
{
// limits
if (i == 9)
{
i = 0;
if (++j == 9) return true;
}
// skip clues
while (getTile(i, j) != 0)
{
i++;
// limits
if (i == 9)
{
i = 0;
if (++j == 9) return true;
}
}
for(int x=1; x <= 9; x++)
{
if(setTileIfValid(i, j, x))
{
Log.d("SUDOKU: ", "set["+i+"]["+j+"] at value: "+x);
if(solveSudoku(i+1, j, getActualPuzzle()))
{
return true;
}
else
{
// backtrack
Log.d("SUDOKU: ", "***************** BACKTRACK *******************");
setTile(i, j, 0);
Log.d("SUDOKU: ", "*** setTile "+i+" "+j+" a 0 ***");
}
}
}
return false;
} |
GetTile must return the value from Sudoku[row][col]
SetTile must set the value at Solution[row][col]
SetTileIfValid must set the value at Solution[row][col] if value is valid for the adressed cell and return true, or else return false
Don't know why you pass the reference of an array you don't use within the scope of SolveSudoku... _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
Back to top |
|
|
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|