i want to generate a simple Sudokugenerator using backtrack. I am stuck / don't know if i used backtracking properly. zahlIstGueltigAufPosition returns if the number zahl is valid (if zahl appears once in the row/column or one of the 9 Boxes).
public static boolean fuelleArray(int y, int x, int zahl){
sudokuArray[y][x]=zahl;
if(zahlIstGueltigAufPosition(y,x,zahl)){
if(x==8 && y<=7 && fuelleArray(y+1,0,1)){
return true;
}else if(x==8 && y==8 && fuelleArray(y,x,zahl)) {
return true;
}else if(x<=7 && y<=8){
if(fuelleArray(y,x+1,1)) {
return true;
}
}
}else{
if(zahl<9 && x<=8 && y<=8 ){fuelleArray(y,x,zahl+1);}
}
return false;
}
The Program gives out:
1 2 3 4 5 6 7 8 9
4 5 6 1 2 3 9 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
Thanks for any help
So this is my solution, there are better ways you can use backtracking to generate sudoku, like just calling fuelleArray(fieldIndex, numberInField). With that, backtracking would be more visible and clear in the code and you won't have to deal, like I had, with the cases when its on the end of a row.
public static boolean fuelleArray(int y, int x, int zahl){
sudokuArray[y][x]=zahl;
if(zahlIstGueltigAufPosition(y,x,zahl)){
//#1
if(x==8 && y<=7){ //if you aren't at the end
if(fuelleArray(y+1,0,1)){ //look if the the next field
return true; //is correct
}
//#2
}else if(x==8 && y==8){ //if I am at the end
return true; //return true, cause at
//zahlIstGueltigAufPosition
//we know its correctly plassed
//by the SudokuRules
}else if(x<=7 && y<=8){ //Just like #1, but there it
if(fuelleArray(y,x+1,1)){ //was to handle the end of a
return true; //row
}
}
}
if(zahl<9 && x<=8 && y<=8 ){ //if we are not correct we
if(fuelleArray(y,x,zahl+1)){ //increase the number in that
return true; //field
}
}else { //if we are at number 9 we put
sudokuArray[y][x]=0; //put it back to zero
//
} //
return false; //and return false
}