逻辑解算算法(适用于Java中的数独)

Question

我的逻辑解算算法存在问题.它很好地解决了大量提示的谜题,它只有少于45条线索的谜题.

这是解决的算法.Immutable是一个布尔值,用于确定是否可以更改该值.cell [row] [col] .possibleValues是名为SudokuCell的类中的LinkedList,用于存储该网格元素可能存在的值.grid.sGrid是拼图的主要int [] []数组.removeFromCells()是一种从网格的行,列和象限中删除值的方法.该代码进一步提供.

第二个for循环仅用于检查单个解决方案.我决定避免递归,因为我真的无法理解它.这种方法现在似乎运作良好.

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

这是removeFromCells()的代码

我认为大多数代码都是不言自明的.第一个for循环从(x,y)的行和列中删除值,第二个循环从象限中删除值.

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

另一个问题点可能是构造可能值的位置.这是我的方法:

第一个for循环创建新的SudokuCells以避免可怕的空指针异常.

sGrid中的任何空值都表示为0,因此for循环会跳过这些值.

SudokuBoard的构造函数调用此方法,因此我知道它正在被调用.

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

我会发布整个文件,但那里有很多不必要的方法.我发布了我认为导致我的问题的内容.

Answer 1

您似乎只构建了一个基于现在解决的简单约束.你需要一个完整的回溯,以解决提示较少的谜题.有些情况下,如果没有回溯,你无法真正解决.

或者,您应该尝试实现Knuth算法(Dancing Links)来解决此类问题.理解和实现比回溯算法更复杂,但运行方式更好:).见这里:http://en.wikipedia.org/wiki/Dancing_Links

它也是一个更普遍的问题的算法,它被应用于非常成功地解决数独.

在维基百科上有一篇文章的链接,详细说明了使用约束编程可以解决的实例类型:http://4c.ucc.ie/~hsimonis/sudoku.pdf(可在此处找到:http://en.wikipedia .org/wiki/Sudoku_algorithms).表4非常有趣:).