Sudoku recursion problematic while backtraking. (Brute Force) [duplicate]

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:

1. Find the number of zeros in the sudoku.

2. 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).

3. Then I make a recursive call, end when there are no more zeroes (n is the number of zeros).

4. 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

Answer 1

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

Answer 2

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