java - 逻辑求解算法(Java 数独)

Question

我的逻辑求解算法有问题。它很好地解决了具有大量提示的谜题，它只是解决了少于 45 条线索的谜题。

这是求解的算法。 Immutable 是一个 boolean 值，用于确定该值是否可以更改。 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 真的很有趣 :)。