Sudoku Backtracking Algorithm (Java)
I have created a Sudoku solver that will resolve Sudoku as a human being by checking the possibilities + certain values in the squares corresponding to the square being tested.
(Source: http://pastebin.com/KVrXUDBF )
However, I would like to create a random Sudoku generator (from an empty grid) and therefore decided to use a backtracking algorithm. I understand the concept of backtracking, but one thing confuses me:
How do I know which previous node to return (and modify) once I know a certain solution is not allowed? Should I just go back to the previous node and go through all the possibilities? (And then if that doesn't give the correct answers, return the value before, etc.). This seems like a viable method, but it is also quite ineffective. Is this the correct way to implement the backtracking method, or is there a better way to do it?
Thanks in advance.
More details about backtracking can be found here: http://en.wikipedia.org/wiki/Backtracking
source to share
A Sudoku puzzle can be boiled down to a graph coloring problem, which can be solved with a simple backtrace, such as assigning colors to node (1-9) until it is assumed that all directly connected nodes are not the same color.
Plotting a graph from sudoku : -
There is a straight border between two grid points if they are in the same row or column or square.
Rollback : -
- Assign one color (1 to 9) to node
- Check if there is another direct connected node with the same color
- If a valid color moves to the next node.
- change the color and check again.
- If all color is exhausted back to the previous node.
- Recurse until all nodes are colored.
Once you're done with that, you can start deleting numbers from the grid at random until you think the problem is unsolvable if more numbers are removed.
source to share
A simple way to generate a random Sudoku is to
1) generate a random Sudoku completion, that is, generate a random Sudoku, no squares are empty.
2) Remove numbers from squares 1).
3) Solve Sudoku 2). If there are many solutions please add the number removed in 2).
If there are many more solutions, repeat 3).
1) sample source code:
public int[][] generateRandomCompleteSudoku() {
int[][] sudoku = new int[10];
for(int i = 1; i <= 9; i++) {
sudoku[i] = new int[10];
Arrays.fill(sudoku[i], 0);
}
generateRandomCompleteSudoku(sudoku, 1, 1);
return sudoku;
}
private boolean generateRandomCompleteSudoku(int[][] sudoku, int x, int y) {
if(x > 9) {
x = 1;
y++;
}
//sudoku of the argument is completing sudoku.
//so return true
if(y > 9) {
return true;
}
// enumerate the possible numbers of the pos(x,y).
List<Integer> possibleNumbers = new ArrayList<Integer>();
for(int i = 1; i <= 9; i++) {
boolean possible = true;
//check i is a possible number.
//check there isn't i in the raw of y .
for(int j = 1; j <= x - 1; j++) {
if(sudoku[j][y] == i) {
possible = false;
break;
}
}
//check there isn't i in the column of x(omitted).
//check there isn't i in the group of x,y(omitted).
if(possible) {
possibleNumbers.add(i);
}
}
//sudoku is wrong so return false.(There is no solution of sudoku)
if(possibleNumbers.size() <= 0) {
return false;
}
Collections.shuffle(possibleNumbers);// This gives sudoku randomness.
for(Integer possibleNumber : possibleNumbers) {
sudoku[x][y] = possibleNumber;
// a sudoku is generated, so return true
if(generateRandomCompleteSudoku(sudoku, x + 1, y)) {
return true;
}
}
// No sudoku is generated, so return false
return false;
}
source to share
For a backtracking solution, the first step is to determine the state. So for this problem, I think the most straightforward way is (x,y, blank , num)
with x , y
- this is the position of the current state, blank
is the number of the empty position to the left, and num
is the value you want to fill that position (0 to 9 and 0 means space).
And the return type must be a boolean determining if the move is valid or not (which means if there is any valid solution for this move).
So, the state transition is column by column, row by row: x, y to x, (y + 1) or x, y to (x + 1), 0. Similarly, the space will be from a → a - 1-> ... 0. We have a draft solution:
public boolean move(int x, int y, int blank, int num, int[][]sudoku){
sudoku[x][y] = num;
//checking condition and return if x,y is the last position, code omitted
if(y == sudoku[x].length){
x++;
y = 0;
}else{
y++;
}
for(int i = 1; i < 10; i++){
if(move(x,y,blank,i,sudoku){//Backtrack here
return true;
}
}
if(blank > 0){
if(move(x,y,blank - 1, 0, sudoku){//Backtrack here
return true;
}
}
return false;
}
So, when ever there is a false return from the current state, it goes back to the last state, and the last state will keep checking the next num
one until it finds the right solution (or returns false).
source to share