Sudoku solving algorithm with back
I'm looking to implement a very simple algorithm that uses brute-force back-tracking to solve Sudoku grids. The problem I'm facing is that in my implementation I included two instance variables for a Sudoku class called row and col , which correspond to the row and column of an empty cell in a two dimensional array that represents the Sudoku grid.
When my solve() method executes it first checks to see if there aren't any empty cells, in which case the puzzle is already complete. Otherwise, that same method assigns the row and column of an empty cell to the instance variables row and col of the Sudoku object that contains the grid. Afterwards, the for loop verifies which number can be placed in that empty cell through a method call isSafe(int n) (This method checks to see if the constraints of the puzzle are being met, I can guarantee that it functions perfectly). So, the isSafe() method places a number in the empty cell and then makes a recursive call to the solve() method again on the Sudoku object.
If we hit a constraint that can't be met, then we reassign a 0 to the last row and col that was filled. This is where the problem is found! Since the program is constantly updating the row and col variables then the old instances are lost with each recursive call. I have been trying to figure out how to store this values so the program can undo actions when it back-tracks. I thought about pushing each col and row to a stack but I'm really not sure where to go.
Can somebody tell me what would be a simple way to approach this problem? I'm not including the entire class, if you think it'd be helpful let me know and I'll post it.
class Sudoku {
int SIZE, N, row, col;
int Grid[][];
public boolean solve() {
if (!this.findNextZero()) return true;
for (int num = 1; num <= 9; num++) {
if (isSafe(num)) {
this.Grid[this.row][this.col] = num;
if (this.solve()) return true;
this.Grid[this.row][this.col] = 0;
// this.Grid[oldRow][oldCol] = 0;
}
}
return false;
}
public boolean findNextZero() {
for (int i = 0; i < this.N; i++) {
for (int j = 0; j < this.N; j++) {
if (this.Grid[i][j] == 0) {
this.row = i;
this.col = j;
return true;
}
}
}
return false;
}
public boolean isSafe(int num) {
return !this.usedInRow(num)
&& !this.usedInColumn(num)
&& !this.usedInBox(num);
}
If I were to implement a stack, does the following make sense? After the findNextZero() operations push the row and col integers onto the stack. Keep doing this and then modify the following line of code
this.Grid[this.row][this.col] = 0;
to something like
this.Grid[s.pop][s.pop] = 0;
Is this a reasonable approach?
try this link : Java Sudoku Solver
The implementation is similar to the standard backtracking approach to the eight queens puzzle.
I was able to store the 'row' and 'col' values of the empty cells that I kept loosing with each recursive call by storing them in a Stack instance variable of the Sudoku class. The findNextZero() method pushed the 'row' and 'col' values into two empty stacks. Then, I restructured the rest of the program to access this information through the peek() method, and in case i had to backtrack I simply popped the last two values and set the number on the grid corresponding to those values to 0.
Actually, you don't really need a stack or recursion. You just need an ordered way to visit the cells (see code below). This solution will not give you stackoverflow like a recursive version would.
I would create an initial matrix to label pre-solved cells:
public boolean[][] findSolved(int[][] grid){
boolean[][] isSolved = new boolean[9][9];
for(int i=0; i<9; i++)
for(int j=0; j<9; j++)
isSolved[i][j] = grid[i][j] != 0;
return isSolved;
}
Then go forwards or backwards through the cells based on if you are backtracking:
public boolean solve(int[][] grid){
boolean[][] isSolved = findSolved(grid);
int row, col, k = 0;
boolean backtracking = false;
while( k >= 0 && k < 81){
// Find row and col
row = k/9;
col = k%9;
// Only handle the unsolved cells
if(!isSolved[row][col]){
grid[row][col]++;
// Find next valid value to try, if one exists
while(!isSafe(grid, row, col) && grid[row][col] < 9)
grid[row][col]++;
if(grid[row][col] >= 9){
// no valid value exists. Reset cell and backtrack
grid[row][col] = 0;
backtracking = true;
} else{
// a valid value exists, move forward
backtracking = false;
}
}
// if backtracking move back one, otherwise move forward 1.
k += backtracking ? -1:1
}
// k will either equal 81 if done or -1 if there was no solution.
return k == 81;
}
上一篇: 将SignalR Hub集中到另一个项目
下一篇: 数独求解算法