Sudoku recursion problematic while backtraking. (Brute Force)

Question

Possible Duplicate:
Sudoku solver in java, using backtracking and recursion

I am creating a program that will solve a sudoku using recursion and brute force. My key problem is that I do not understand how I could concievably make it backtrack one it gets stuck.

The general algorithm of the program is the following:

Find the number of zeros in the sudoku.
In the location of the first 0 (getNextEmpty method does this), insert a number(insertnumber checks to make sure a value complies with sudoku rules and returns true if it does).
Then I make a recursive call, end when there are no more zeroes (n is the number of zeros).
If the program reaches a point that it gets stuck, I must backtrack to change a piece. But how is this possible?

The Cell class actually holds the location of the cell to be adjusted in an array of the format [row, column]. It has methods to return the row, column, or smaller grid associated with that cell.

I am not asking for hand-holding or all the code, just a nudge in the right direction will suffice as I am legitimately interested in understanding the recursion.

public static int[][] getSolution(int[][] grid) {
    for (int i = 0; i < 9; i++) {
        System.arraycopy(grid[i], 0, SolveSudoku.grid[i], 0, 9);
    }// end for
    int n = getZeroes();
    return getSolution(n);
}//end getSolution

private static int[][] getSolution(int n) {
    if (n == 0) {
        return grid;        
    }//end if
    Cell cell = getNextEmpty();
    boolean fits = false;
    for (int i = 0; i <= 9; i++) {
        fits = insertNumber(cell, i);
        if (fits) {
            break;
        }else {
            //I do not understand what I should do here
        }
    }//end for
    return getSolution(n - 1);
}//end getSolution

yes, the intention is to try every combination until it works. Rather than a calculated approach to solving the sudoku. — Tony, Mar 01 '12 at 00:22
Have you done some back-of-the-envelope math to find out if this is halfway reasonable to brute strength? I don't know the problem too well, but this strikes me as something that could spin for a few hundred or thousand years if you get a "hard" puzzle. Or much, much longer if you get an impossible one (for which you'll have to enumerate every wrong path). — yshavit, Mar 01 '12 at 00:38
Yes, we are required to solve it this way. there are specifically 4 puzzles me must solve, each will take only a few miliseconds. I know that worst case scenario puzzles may take upwards of 650,000 attempts. This is now the case for me however. — Tony, Mar 01 '12 at 00:43
Are both method headers provided to you in your assignment or did you write one of them? — Pradeep Gollakota, Mar 01 '12 at 00:51
@yshavit: Even a completely empty sudoku needs just about 50ms to be solved on my webbook. — Robert, Mar 01 '12 at 01:19
It would take about 3.4 thousand million years to find all solutions though. — Robert, Mar 02 '12 at 23:26
The same question was discussed [in this question](http://stackoverflow.com/questions/9404673/sudoku-solver-in-java-using-backtracking-and-recursion/9406646#9406646). Have a look. Hearing the same class, huh? — niklas, Mar 01 '12 at 14:29

score 2 · Accepted Answer · answered Mar 01 '12 at 00:31

2

A nudge in the right direction. Your approach needs a little tweaking since you're not keeping track of all the information you need to solve the grid.

private static int[][] getSolution(int n) {
    if (n == 0) {
       return grid;        
    }//end if

    Cell cell = getNextEmpty();
    boolean fits = false;
    for (int i = 0; i <= 9; i++) {
        fits = insertNumber(cell, i);
        if (fits) {
            break; // means i fits in Cell
        } else {
            // i doesn't fit... try the next i
            // don't need to do anything
        }
    }//end for
    if (!fits) {
        // There are no numbers that fit in this Cell
        // What should happen?
        // Did I make a bad guess?
        // How do I BACKTRACK and correct a previous guess?
    }
    return getSolution(n - 1);
}//end getSolution

answered Mar 01 '12 at 00:31

Pradeep Gollakota

2,161
16
24

I was thinking along these lines. I had considered creating an arraylist with a record of all of the moves and backtrack when it runs into a problem. However, was told by my professor "This is not necessary. you are only making 1 "move". The recursive call makes all of the other moves." This seems to be throwing me off. – Tony Mar 01 '12 at 00:38
Take a look at the pseudocode in [Backtracking](http://en.wikipedia.org/wiki/Backtracking#Pseudocode). You almost have the right idea. You just need to get your loop into the right place. – Pradeep Gollakota Mar 01 '12 at 00:46
Sorry... I meant to say you need to get your recursive call into the right place... not your loop – Pradeep Gollakota Mar 01 '12 at 00:56
hmm, this is really making me think about this, thank you for the tip. Let me see what I can do. – Tony Mar 01 '12 at 01:01
Another hint: What is `i`? If `i` fits, what should you do? Where did they put the recursive call in the pseudocode I linked you? – Pradeep Gollakota Mar 01 '12 at 01:07
oh wow, the recursive call is in the while. If i works, I am done with that specific tile of the grid. If i does not work, I should try the next. However if i does not work, I need to go back and try another with the i it had used + 1. Would it be incorrect to use some type of alrraylist to store the other moves and go back? or would it be better to try to see if it solves if the rest of the puzzle would solve for that i? then increment if it does not? hmmm – Tony Mar 01 '12 at 01:09
And how do you determine if `i` works or not? This is related how you "go back." But you're pretty much onto the solution now. – Pradeep Gollakota Mar 01 '12 at 01:13
well, I am thinking that you would have to make the recursive call in the if statement nested withing the loop. I would make the method return null if It does not have find a solution. Then increment i if it returns null. But now my question is, how could I determine if there is a solution? Your help has already totally enlightened me on this. wow – Tony Mar 01 '12 at 01:18
I've moved this discussion into [chat](http://chat.stackoverflow.com/rooms/8372/discussion-between-pradeep-gollakota-and-antonio-diaz) which is better venue for lengthy conversations – Pradeep Gollakota Mar 01 '12 at 01:22
+1 for taking the time to do mentoring on a homework question – Mikeb Mar 01 '12 at 14:13

score 1 · Answer 2 · answered Mar 01 '12 at 00:27

1

Generally in a recursive brute force, you use syntax similar to the code below. That is done because you can count that after you did any action, that is the new "starting position". So it would be similar to this:

private void Guess(int[][] grid)
{
    if(/**grid is a solution **/)
        //signal success
    else
    {
        if(/*seed out any bad, unacceptable answers you may have missed*/)
            return;//this includes cases when there are no more zeros
        //for every possible move,
        //make a modified grid, with one move done, and call
        Guess(ModifiedGrid);//for every possible move, generally you can modify
        //grid itself, because its passed by value
    }
}

answered Mar 01 '12 at 00:27

It's generally better NOT to work with a static grid, because backtracking is difficult, I here use a standard approach with the grid being passed by value. The only limit is that it may run out of memory, but in theory it's the optional way of brute forcing. – Mar 01 '12 at 00:36
Unfortunatly I am required to use this static grid for the assignment. – Tony Mar 01 '12 at 00:44
you can then make another static array that will contain all changes you make, something like a Map, basically you enter the change #, it returns the position x,y of the change you made. You can then undo that change. The code for this will probably be a bit longer though, but I hope you understand. If I helped please vote up! – Mar 01 '12 at 00:58
He doesn't actually need to do any of that... he's really close to a working solution... its a matter adding like 5 lines of code. What you suggested would actually work, but that's not the way a dancing links algorithm is supposed to work. You let your recursion handle correcting bad guesses. – Pradeep Gollakota Mar 01 '12 at 01:02
Please join me in [chat](http://chat.stackoverflow.com/rooms/8372/discussion-between-pradeep-gollakota-and-antonio-diaz) if you're able to and wish to discuss more. – Pradeep Gollakota Mar 01 '12 at 01:22

Sudoku recursion problematic while backtraking. (Brute Force)

2 Answers2