Sudoku solving algorithm with back-tracking

Question

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?

Counterman

What is in method isSafe, post the code first. – Amaliaamalie

posted! the three methods being called from isSafe() simply check if the constraints of a sudoku problem are met by the grid – Counterman

Using a stack would be a good approach. – Electrotherapeutics

I think you either need to call a recursive function or add unsolved nodes to a stack as you go and pop if a constraint can't be met – Origin

Store the moves as a string "UudlLrR" could mean "Moved block up, moved up, moved down, moved left, moved block left, moved right, moved block Right", then backtracking the moves is simply a matter of looking at the last character in the string and doing the reverse of it then popping that last character off the string. – Wassail

@Macalaca. Yeah, that sounds reasonable. – Origin

Can you post the complete code? – Diplegia

Answer 1

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

Origin

That's a pretty clever way to solve sudoku using limited memory. None of the solvers I've written have used a specific sequence of cells to fill though (generally I write them to fill the cell with the fewest possibilities at any given step, but I've also written one that places the digit with the fewest possible locations: that's to say when it backtracks to a given point it will place the same digit again in a different place) – Renfred

@JeremyList yeah luckily the brute force way is not the fastest way to solve Sudoku -- the puzzle wouldn't be very fun for humans if they could brute force a solution faster than thinking of something clever. – Origin

@JeremyList, if your interested in writing solvers for some of the more advanced techniques, check out sudokuwiki.org/sudoku.htm. It explains nearly every type you can think of. Also, a long time ago I wrote some in Python if you're interested: github.com/bcorso/sudoku-solver/tree/master/sudoku_solver/src. – Origin

Answer 2

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.

Counterman