数独逻辑求解算法 (Java)

Question

我决定为我的数独应用程序编写一个逻辑求解算法。我写的内容适用于有限数量的网格值，但递归很快就停止了。

我的方法的作用： addToThirdDimension()：三维数组存储可以放入逻辑网格[x][y]处的网格值中的任何可能的值。该方法刷新三维数组。它通过测试每个网格索引中的值 1-9 来实现此目的，如果有效，则会将该数字添加到数组中。如果不是，则将该值设置为零。

checkValues()：检查三维网格中还剩下多少种可能性。它遍历逻辑网格并返回网格中非零值的数量。

checkSingleValue(int row, int col)：检查logicGrid[row][col]中是否只剩下一个值（如果剩下一个值，则它是[row]处的网格元素的唯一可能，col]）。它返回该网格位置中的非零值的数量。

getSingleValue(int row, int col)：返回logicGrid[row][col]中剩下的单个数字。

immutableValues：一个二维布尔数组，存储特定网格元素是否不可变。如果它是不可变的，则解决方法不应触及它。

public boolean solveWithLogic(){

    addToThirdDimension();
    if(checkValues() == 0){
        return true;
    }

    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            if(!immutableValues[row][col]){
                if(checkSingleValue(row, col) == 1){
                    sGrid[row][col] = getSingleValue(row, col);
                    setValues[row][col] = true;
                    addToThirdDimension();
                }
            }
        }
    }

    if(checkValues() != 0){
        solveWithLogic();
    } else{
        return true;
    }

    return false;
}

我看不出我哪里出了问题。经过一定次数的尝试后，即使应该有更多的可能性， checkValues 也会返回 0。这是 addToThirdDimension() 的代码，因为我确信如果有问题，就在这里。

sGrid 是存储拼图值的主要二维整数数组。

public void addToThirdDimension(){

    logicGrid = new int[9][9][9];

    for(int x = 0; x < 9; x++){
        for(int y = 0; y < 9; y++){
            for(int z = 0; z < 9; z++){
                logicGrid[x][y][z] = z + 1;
            }
        }
    }

    int[][] temp1 = sGrid;

    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            if(setValues[row][col]){
                for(int i = 0; i < 9; i++){
                    logicGrid[row][col][i] = 0;
                }
            } else{
                for(int i = 1; i <= 9; i++){
                    temp1[row][col] = i;
                    if(!isColumnValid(col, temp1) && !isRowValid(row, temp1) &&
                            !isQuadrantValid(row, col, temp1){
                        logicGrid[row][col][i-1] = 0;
                    }
                }
            }
            temp1[row][col] = sGrid[row][col];
        }
    }
}

目前该代码效率还不太高。我希望在开始最小化求解时间之前让它发挥作用。

Answer 1

我要做的第一件事是创建一个 SudukoCell 对象，在其中存储您可能的值。然后创建一个带有 SudukoCells 二维数组的 SudukoBoard。还给它一个 SudukoAreas 数组。一个区域用于行，一个区域用于列，一个区域用于块。

适当添加您的数独细胞。

这将帮助你巩固你的跑腿工作并防止愚蠢的错误。

然后，每次解出一个数字时，您都可以转到每个区域中的单元格，并从中删除您解出的数字。