1

i'm trying to write a Sudoku solver which will return only the first possible solution. i managed to print all possible solutions with void methods but i can't stop on the first find.

i know the preferred way is to switch to boolean methods and return true up the tree - but i can't find the right way to write it.

any way i tried always give compilation errors (method must return boolean).

public boolean recursiveSolve(int line, int column) {
    if(line == N) // N is the board size (9)
        return true;
    // if Cell is not empty - continue
    if(board1.getCell(line, column) != 0) { 
        return nextCell(line, column);
    }
    // if Cell empty - solve
    else { 
        for(int i = 1; i <= N; i++) {
            board1.setCell(line, column, i); // set value to cell
            if(board1.boardIsOk())           // check if the board is legal
                return nextCell(line, column); // continue
        }
        board1.setCell(line, column, 0);     // backtrack
    }
}

private boolean nextCell(int line, int column) {
    if(column < 8)
        return recursiveSolve(line, column+1); // progress up the row
    else
        return recursiveSolve(line+1, 0);      // progress down the lines
}

Any help will be most appreciated.

Ben Kaplan
  • 13
  • 1
  • 3
  • Shouldn't a Sudoku have only one solution? – Emil Vikström Jan 27 '12 at 22:36
  • where is .boardIsOk() coming from? Also, something tells me that you should be storing nextCell to a variable, and checking the value of that var on each run of your for loop. Once the val hits something you want, then return. – Kristian Jan 27 '12 at 22:39
  • @EmilVikström: Concider one activates this method with an empty board.. – amit Jan 27 '12 at 22:39

2 Answers2

9

Here is some pseudocode for most recursive backtracking problems.

If you are already at a solution, report success.

for (every possible choice in the current position ) {

Make that choice and take one step along the path.

Use recursion to solve the problem from the new position.

If the recursive call succeeds, report the success to the next higher level.

Back out of the current choice to restore the state at the beginning of the loop.

}

Report failure.

Here is some actual code based on a lecture from Stanford. I re-wrote it in java and included comments.

Boolean SolveSudoku(int[][] grid)
{
    int row, col;

    if(!FindUnassignedLocation(grid, row, col))
        //all locations successfully assigned
        return true;

    for(int num = 1; num <= 9; num++)
    {
        //if number is allowed to be placed in the square
        if(NoConflicts(grid, row, col, num))
        {
            //place the number in the square
            grid[row][col] = num;

            //recur, if successful then stop
            if(SolveSudoku(grid))
                return true;

            //undo and try again
            grid[row][col] = UNASSIGNED;
        }
     }
     //this triggers backtracking from early decisions
     return false;
}

You just need to implement a few methods, which are pretty trivial.

theDazzler
  • 1,039
  • 2
  • 11
  • 27
  • thanks guys. indeed the whole structure of my code was wrong, so i couldn't end the backtracking when i wanted. changing to the pattern above works like a charm. – Ben Kaplan Jan 28 '12 at 12:10
1

Change

        if(board1.boardIsOk())           // check if the board is legal
            return nextCell(line, column); // continue

into

        if(board1.boardIsOk()) {          // check if the board is legal
            boolean solved = nextCell(line, column); // continue
            if (solved) {
                return true;
            ]
        }
    ...
    return false;
Joop Eggen
  • 107,315
  • 7
  • 83
  • 138