c - 解决数独的算法

Question

我正在尝试编写一种算法来解决扩展数独问题。我设法找到了 9x9 数独的解决方案，但是当我尝试扩展它时，我的程序返回“无解决方案”，我不知道哪里出了问题。也许有人可以建议我在哪里犯了错误？

#include<stdio.h>
#include<algorithm>

int sudoku[15][9] = {{0, 0, 0, 0, 0, 0, 0, 0, 9},
                    {4, 7, 0, 0, 0, 0, 0, 0, 0},
                    {0, 0, 0, 5, 6, 2, 0, 0, 3},
                    {0, 6, 0, 0, 0, 0, 0, 0, 0},
                    {0, 0, 4, 0, 0, 3, 0, 6, 0},
                    {0, 5, 9, 0, 0, 0, 0, 0, 0},
                    {0, 0, 0, 2, 0, 0, 0, 0, 0},
                    {6, 0, 0, 4, 0, 0, 0, 0, 0},
                    {0, 4, 8, 0, 0, 0, 6, 0, 0},
                    {0, 0, 4, 0, 0, 0, 0, 0, 0},
                    {0, 2, 0, 0, 0, 0, 1, 0, 0},
                    {0, 9, 1, 0, 0, 4, 0, 0, 5},
                    {0, 0, 0, 0, 0, 0, 0, 0, 0},
                    {4, 0, 0, 6, 0, 0, 0, 0, 5},
                    {5, 0, 0, 0, 0, 0, 8, 6, 0}};

bool isPossibleToInsert(int array[][9], int v, int x, int y){
    int rows = (x / 3) * 3;
    int columns = (y / 3) * 3;
    for (int i=0; i<9; i++){
            if (i < 3){
                    for (int j=0; j<7; ++j){
                            if (sudoku[j][y] == v) return false;
                    }
            }
            if (i > 5){
                    for (int j=8; j<=14; ++j){
                            if (sudoku[j][y] == v) return false;
                    }
            }
            if (array[x][i] == v) return false;
            if (array[i][y] == v) return false;
            if (array[rows + i%3][columns + i/3] == v) return false;
    }
    return true;
}

bool checkNextCell(int orginal[][9], int copy[][9], int x, int y);
bool tryToSolve(int sudoku[][9], int temp[][9], int x_val, int y_val){
    if (sudoku[x_val][y_val] == 0){
            for (int i=1; i<=9; ++i){
                    if (isPossibleToInsert(temp,i,x_val,y_val)){
                            temp[x_val][y_val] = i;
                            if (checkNextCell(sudoku,temp,x_val,y_val)) return true;
                    }
            }
            temp[x_val][y_val] = 0;
            return false;
    }
    return checkNextCell(sudoku,temp,x_val,y_val);
}

bool checkNextCell(int orginal[][9], int copy[][9], int x, int y){
    if ((x == 8) && (y == 8)) return true;
    else if (x == 8) return tryToSolve(orginal,copy,0,y+1);
    else return tryToSolve(orginal,copy,x+1,y);
}

int main(){
    /*int sudoku[15][9] = {{0, 0, 0, 0, 0, 0, 0, 0, 9},
                        {4, 7, 0, 0, 0, 0, 0, 0, 0},
                        {0, 0, 0, 5, 6, 2, 0, 0, 3},
                        {0, 6, 0, 0, 0, 0, 0, 0, 0},
                        {0, 0, 4, 0, 0, 3, 0, 6, 0},
                        {0, 5, 9, 0, 0, 0, 0, 0, 0},
                        {0, 0, 0, 2, 0, 0, 0, 0, 0},
                        {6, 0, 0, 4, 0, 0, 0, 0, 0},
                        {0, 4, 8, 0, 0, 0, 6, 0, 0},
                        {0, 0, 4, 0, 0, 0, 0, 0, 0},
                        {0, 2, 0, 0, 0, 0, 1, 0, 0},
                        {0, 9, 1, 0, 0, 4, 0, 0, 5},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0},
                        {4, 0, 0, 6, 0, 0, 0, 0, 5},
                        {5, 0, 0, 0, 0, 0, 8, 6, 0}};*/
    int arrayMain[9][9];
    std::copy(sudoku+7, sudoku+15, arrayMain);
    if (tryToSolve(sudoku,arrayMain,0,0)){
            for (int i=0; i<9; ++i){
                    for (int j=0; j<9; ++j){
                            printf("%d ",arrayMain[i][j]);
                    }printf("\n");
            }
    }
    else{
            printf("No solution");
    }
    return 0;
}

编辑:
对不起，我没有正确解释问题。在上面的示例中，数独必须是两个独立的 9x9 数独(第 1-9 行是第一个，第 7-15 行是另一个)。

Answer 1

所以你有一个 super 数独，它由在第 6-8 行重叠的两个数独组成(我从 0 开始计数)。

问题是你不能像你的代码那样独立解决它们。为什么？因为它们不是两个独立的数独。根据定义，数独的解决方案是唯一的，否则它不是数独。 super 数独也是如此。但是，如果您独立地查看重叠的数独，那么解决方案(在大多数情况下)并不是唯一的。因此，整个 super 数独必须作为一个谜题来解决，而不是两个独立的谜题。换句话说，您的算法找到了上层数独的解决方案，这使得下层数独无法解决。

回溯法也适用于 super 数独，算法与简单数独非常相似。但是，当您到达第 6-8 行时，您必须针对上部和下部数独来测试它们。之后你继续正常解决第二个数独。