Logical solution algorithm (applicable to Sudoku in Java)

I have a problem with my logic algorithm It solves the problem of a large number of hints, which is only a problem with less than 45 clues

This is the algorithm for solving Immutable is a Boolean value that determines whether the value can be changed cell [row] [col] . Possiblevalues is a LinkedList in a class named sudokucell, which is used to store the possible values of the grid element grid. Sgrid is the main int [] [] array of the puzzle Removefromcells () is a method to delete values from rows, columns, and quadrants of a grid This code is further provided

The second for loop is only used to examine a single solution I decided to avoid recursion because I really can't get my mind This method seems to work well 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 self - evident The first for loop deletes the value from the row and column of (x, y), and the second loop deletes 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 may be building possible values This is my method:

The first for loop creates new Sudoku cells to avoid the dreaded null pointer exception

Any null values in sgrid are represented as 0, so the for loop will skip these values

Sudokuboard's constructor 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,grid.sGrid[row][col]);
                immutable[row][col] = true;
            }
        }
    }
}

I will publish the whole document, but there are many unnecessary methods there I posted what I thought was the problem that caused me

Solution

You seem to have only established a simple constraint to solve the present problem You need a complete heel to solve the puzzle with fewer hints In some cases, you can't really solve without backtracking

Alternatively, you should try to implement Knuth's algorithm (dancing links) to solve this type of problem Understanding and implementation are more complex than backtracking algorithm, but the operation mode is better:) See: http://en.wikipedia.org/wiki/Dancing_Links

It is also a more general problem algorithm, which is applied to solve Sudoku well

There is a link to an article on Wikipedia detailing what types of examples can be solved using constraint programming: http://4c.ucc.ie/ ~hsimonis/sudoku. Pdf (found here: http://en.wikipedia.org/wiki/Sudoku_algorithms ）. Table 4 is really interesting:)