Sudoku backtracking solution

Question

I am looking to implement a very simple algorithm that uses brute force backtracking to solve Sudoku networks. The problem I'm facing is that in my implementation, I included two instance variables for the Sudoku class called row and col , which correspond to the row and column of the empty cell in the two-dimensional array that represents Sudoku.

When my solve() method executes it, it first checks to see if there are no empty cells, in which case the puzzle is already completed. Otherwise, the same method assigns the row and column of the empty cell to the variables of the row and col instance of the Sudoku object that contains the grid. After that, the for loop checks which number can be placed in this empty cell by calling the isSafe(int n) method (this method checks if the puzzle restrictions are met, I can guarantee that it works fine). Thus, the isSafe() method puts the number in an empty cell and then recursively calls the solve() method again on the Sudoku object.

If we click on a constraint that cannot be met, then we reassign a 0 last row and col that was filled. That's where the problem is found! Since the program constantly updates the row and col variables, then the old instances are lost with every recursive call. I am trying to figure out how to save these values ​​so that the program can undo actions when it is reversed. I was thinking about pushing each col and row onto the stack, but I'm really not sure where to go.

Can someone tell me what would be an easy way to approach this problem? I do not include the whole class, if you think that it would be useful, let me know and I will publish 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 integers row and col findNextZero() stack. Keep doing this, and then change 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 smart approach?

Answer 1

You really don't need a stack or recursion. You just need an ordered way to visit cells (see code below). This solution will not give you stackoverflow as a recursive version.

I would create an initial matrix for marking the pre-allowed 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 forward or backward through the cells based on if you go back:

 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; } 

Answer 2

try this link: Java Sudoku Solver

The implementation is similar to the standard approach to the reverse approach to the puzzle of eight queens.

Answer 3

I managed to save the "row" and "col" values ​​of the empty cells, which I continued to lose with each recursive call, storing them in a Sudoku class Stack instance variable. The findNextZero () method moved the "row" and "col" values ​​to two empty stacks. Then I restructured the rest of the program to access this information using the peek () method, and in case I had to back out, I just pulled out the last two values ​​and set the grid number corresponding to these values ​​to 0.