Logic Solving Algorithm (for Sudoku in Java)

Question

I'm having issues with my logic solving algorithm. It solves puzzles with a large number of hints very well, it just has issues with puzzles that have less than 45 clues.

This is the algorithm for solving. Immutable is a boolean that determines whether or not that value can be changed. cell[row][col].possibleValues is a LinkedList within a class called SudokuCell that stores the values that are possible for that grid element. grid.sGrid is the main int[][] array of the puzzle. removeFromCells() is a method that removes values from the row, column, and quadrant of the grid. That code is provided further down.

The second for loop is just for checking for a single solution. I decided to avoid recursion because I really can't get my head around it. This method seems to be working well enough for now.

public boolean solve(){

    for(int i = 0; i < 81; i++){
        for(int row = 0; row < 9; row++){
            for(int col = 0; col < 9; col++){
                if(!immutable[row][col]){
                    if(cell[row][col].getSize() == 1){
                        int value = cell[row][col].possibleValues.get(0);
                        grid.sGrid[row][col] = value;
                        immutable[row][col] = true;
                        removeFromCells(row, col, value);
                    }
                }
            }
        }
    }


    int i = 0;
    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            if(grid.sGrid[row][col] == 0){
                i++;
            }
        }
    }

    if(i != 0){
        return false;
    } else{
        return true;
    }
}

This is the code for removeFromCells()

I think most of the code is pretty self-explanatory. The first for loop removes the value from the row and column of (x, y), and the second loop removes the value from the quadrant.

public void removeFromCells(int x, int y, int value){

    /*
     * First thing to do, find the quadrant where cell[x][y] belong.
     */

    int topLeftCornerRow = 3 * (x / 3) ;
    int topLeftCornerCol = 3 * (y / 3) ;

    /*
     * Remove the values from each row and column including the one
     * where the original value to be removed is.
     */
    for(int i = 0; i < 9; i++){
        cell[i][y].removeValue(value);
        cell[x][i].removeValue(value);
    }


    for(int row = 0; row < 3; row++){
        for(int col = 0; col < 3; col++){
            cell[topLeftCornerRow + row][topLeftCornerCol + col].removeValue(value);
        }
    }
}

Another problem spot could be where the possible values are constructed. This is the method I have for that:

The first for loop creates new SudokuCells to avoid the dreaded null pointer exception.

Any null values in sGrid are represented as 0, so the for loop skips those.

The constructor for SudokuBoard calls this method so I know it's being called.

public void constructBoard(){

    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            cell[row][col] = new SudokuCell();
        }
    }

    immutable = new boolean[9][9];

    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            immutable[row][col] = false;
            if(grid.sGrid[row][col] != 0){
                removeFromCells(row, col, grid.sGrid[row][col]);
                immutable[row][col] = true;
            }
        }
    }
}

I would post the entire file, but there are a lot of unnecessary methods in there. I posted what I think is causing my problems.

Answer 1

You seem to have built only a simple constraint based solved for now. You need a full backtracking one in order to solve puzzles with less hints. There are some cases that you can't really solve without backtracking.

Alternatively you should try to implement Knuth's algorithm (Dancing Links) for solving this type of problems. It's more complicated to understand and implement than a backtracking algorithm but it's running way better :). See here: http://en.wikipedia.org/wiki/Dancing_Links

It's also an algorithm for a more general problem and it was applied to solving sudoku quite successfully.

On wikipedia there is a link to an article detailing what type of instances are possible to solve using constraints programming: http://4c.ucc.ie/~hsimonis/sudoku.pdf (found from here: http://en.wikipedia.org/wiki/Sudoku_algorithms). The Table 4 is really interesting :).