Sudoku recursion with backtracking

Question

I am trying to solve any given sudoku puzzle using a recursive backtracking algorithm. I'm having two problems with my sudoku solver. First off, it solves for the puzzle, however it recurses back up and unsolves it in the process (solves in around 4718 recurses and carries on for another 10000 or so back up for some reason). The second problem stems from my attempt to fix this. I use a global matrix solution to hold the solution once I find it, verifying I have found it using an isSolved method that looks like this:

  public static boolean isSolved(int[][]puzzle){
            for(int i = 0; i<9; i++){  //y rotation
                    for(int j = 0; j<8; j++){
                            if(puzzle[i][j]==0){
                                    return false;
                            }
                    }
            }
            return true;
    }

where, in my puzzle, a block with a 0 in it is equivalent of it being empty. However this seems to also get reset although however I cannot find where this is being reset. Any pointers or suggestions or pointers at where I should look?

Here is my solve method, I have annotated important lines

  public static int[][] solve(int[][]puzzle, int x, int y){
            System.out.println("RecrDepth:  " + recDepth);
            recDepth++;
            //using backtracking for brute force power of the gods(norse cause they obviously most b.a.
            ArrayList<Integer> list = new ArrayList<Integer>();
            //next for both  x and y
            int nextx = getNextx(x);
            int nexty = getNexty(x, y);
            while(puzzle[y][x] != 0){  //progress until blank space
                    x = nextx;
                    y = nexty;
                    if(isSolved(puzzle)){
                            System.out.println("resetting solution improperly");
                            solution = puzzle;
                            return puzzle;
                    }
                    nextx = getNextx(x);
                    nexty = getNexty(x, y);
            }
            for(int i = 1; i<10; i++){
                    if(isTrue(puzzle, y, x, i))  //isTrue checks column, row and box so we dont go down unnecessary paths
                            list.add(i);
            }
            for(int i=0; i<list.size(); i++){  //iterating through options in open squre recursing for each one
                    puzzle[y][x]= list.get(i);
                    if(isSolved(puzzle)){
                            System.out.println("Resetting Solution");  //appears to reset solution here but only once that I see in print out
                            solution = puzzle;
                            return puzzle;
                    }
                    System.out.print("=");
                    puzzle = solve(puzzle, nextx, nexty);
                    puzzle[y][x] = 0;//clear spot upon backtracking THIS WAS WHAT I WAS MISSIN
            }
            return puzzle;
    }

Thank you for your time again, the full code and readin file is on github at wechtera/ssolverOO it is the ssolver.java file and the readin is ssolverin.txt

Solution

If I understood correctly your code, the problems seems to lay on the fact that the recursion is not well implemented, in the sense that your program will keep looping the last for loop even after it has found the right answer.

Say for instance that in the first blank square, the right number is a 4. But the possible list of numbers (at that point in time) that your program is considering is {2, 4, 6, 7}. In this case, what it seems to happen, is that it will find indeed the right answer at 4, and it will generate the correct output. But it will still check for 6 and 7. And since it will (of course) fail to find any answer, it will leave the inputs blank, giving you back the original board.

Now, although I think you had to some extent the right idea in setting a global variable to store the actual answer. The problem is that you're not generating a copy of the array, and you're simply copying the pointer (reference) to it.

You could simply create a copy method to actually copy the entire array, but keep in mind that even if you do generate the correct answer, your algorithm will still needlessly loop and waste time.

For reference, here's the solve method I wrote, where my isValid() method is equivalent to your isTrue() :

public static final int SIZE = 9;

public static boolean solve(int[][] s) {

    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (s[i][j] != 0) {
                continue;
            }
            for (int num = 1; num <= SIZE; num++) {
                if (isValid(num, i, j, s)) {
                    s[i][j] = num;
                    if (solve(s)) {
                        return true;
                    } else {
                        s[i][j] = 0;
                    }
                }
            }
            return false;
        }
    }
    return true;
}

Comments

[Adam Wechter]

Thank you so much, this clears up so many things. It looks like using a boolean recursive method for solving it is the better answer. Your insight is greatly appreciated!

[Gyan]

Good reads : stackoverflow.com/questions/15332134/… , heimetli.ch/ffh/simplifiedsudoku.html

[dynamic]

@Allbeert: This is a very interesting solution that slightly differs from the general approach of solving backtracking problems: you can find the general approach here (from page 3 and on) see.stanford.edu/materials/icspacs106b/… The interesting thing is that in your solution the final return true is completly inverted w.r.t. the general solution