-3

所以我尝试通过回溯算法来实现数独。我不明白为什么我的代码没有给出预期的输出。

我所做的是，我创建了一个循环，它在其中检查数独中的空单元格（用 0 表示）。当它找到它时，它的坐标被传递给一个名为 possibleEntriescheck() 的函数。此函数写入一个名为 possibleEntries[9] 的全局声明数组，这些数字可能填充到最初传递坐标的单元格中。

我从这些视频中学到了这个算法： https://www.youtube.com/watch ?v=NuodN41aK3g https://www.youtube.com/watch?v=QI0diwmx3OY

预期的输出是一个已解决的数独。它没有按预期执行。相反，它冻结了。一点帮助就意味着很多。谢谢你。

#include <stdio.h>
#include <stdlib.h>
int board[9][9] = {
                  {3, 0, 6, 5, 0, 8, 4, 0, 0},
                  {5, 2, 0, 0, 0, 0, 0, 0, 0},
                  {0, 8, 7, 0, 0, 0, 0, 3, 1},
                  {0, 0, 3, 0, 1, 0, 0, 8, 0},
                  {9, 0, 0, 8, 6, 3, 0, 0, 5},
                  {0, 5, 0, 0, 9, 0, 6, 0, 0},
                  {1, 3, 0, 0, 0, 0, 2, 5, 0},
                  {0, 0, 0, 0, 0, 0, 0, 7, 4},
                  {0, 0, 5, 2, 0, 6, 3, 0, 0},
                  };
int possibleEntries[9];
void possibleEntriescheck(int i, int j)
{
    int x,a=0,k,l,y;
    for(x=0;x<9;x++)
        possibleEntries[x]=0;
    for(x=0;x<9;x++)
    {
        if(board[i][x]!=0)
            possibleEntries[board[i][x]-1]=1;
    }

    for(x=0;x<9;x++)
    {
        if(board[x][j]!=0)
            possibleEntries[board[x][j]-1]=1;
    }

    if(i==0 || i==1 || i==2)
        k=0;
    else if(i==3 || i==4 || i==5)
        k=3;
    else
        k=6;

    if(j==0 || j==1 || j==2)
        l=0;
    else if(j==3 || j==4 || j==5)
        l=3;
    else
        l=6;

    for(x=k;x<k+3;x++)
    {
        for(y=l;y<l+3;y++)
            if(board[x][y]!=0)
                possibleEntries[board[x][y]-1]=1;
    }
    for(x=0;x<9;x++)
    {
        if(possibleEntries[x]==0)
            possibleEntries[x]=x+1;
        else
            possibleEntries[x]=0;
    }
}
int isFull()
{
    int i,j;
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            if(board[i][j]==0)
                return 0;
        }
    }
    return 1;
}
void solveSudoku()
{
    int i,j,x,b=0,k;
    if(isFull())
    {
        printf("The sudoku board is:\n");
        for(i=0;i<9;i++)
        {   
            for(j=0;j<9;j++)
                printf("\t%d",board[i][j]);
            printf("\n");
        }
    }
    else
    {
        for(i=0;i<9;i++)
        {
            for(j=0;j<9;j++)
            {
                if(board[i][j]==0)
                {
                    possibleEntriescheck(i,j);
                    for(x=0;x<9;x++)
                    {
                        if(possibleEntries[x]!=0)
                        {
                            board[i][j]=possibleEntries[x];
                            solveSudoku();
                            board[i][j]=0;
                        }
                    }   
                }
            }
        }
    }
    return;
}
int main()
{
    solveSudoku();
}
4

1 回答 1

2

您错误地实施了回溯。正如视频中所解释的，实际的算法应该是这样的：

solve():
    if the sudoku is solved
        print field
        terminate

    x,y = the next vacant field

    for each possible value in that field
        assign value to x,y
        call solve() recursively to try with the assigned value

    clear vacant field

现在您的代码所做的是

solve():
    if the sudoku is solved
        print field
        return

    for each field in the sudoku
        if field is vacant
            for each possible value
                assign value
                solve recursively
                reset field to unassigned

现在这实际上确实解决了数独问题。但是这种方法有两个问题：
A : 一旦解决了数独，它就不会终止。实际上这个错误也出现在视频中的代码中。递归调用中的简单return将终止当前调用的方法并继续递归“上面的一次调用”。因此，基本上该算法以所有可能的方式解决数独（假设有多个，否则它只是尝试任何可能的分配值的方式）。
乙: 这个比较严重。您的算法不仅会生成所有可能的解决方案，而且还会尝试分配它可能找到的值的每个顺序。开销是巨大的，也是您的代码根本不会终止的原因。解决一次数独问题已经花费了相当长的时间，但是您的代码会花费无数次。

如果你解决了这些问题，你的代码应该可以找到，只要其余的都正确实现。我还建议优化空字段的搜索和字段是否为空的测试，因为这些可以相当简单地完成并且会提供一些加速。在开始时生成一个空字段列表，对其进行迭代（每个递归级别一个字段）并在处理整个列表后终止。例如：

solve(vacant, count):
    if count == 0
        print the field
        terminate

    x, y = vacant[count]
    count++

    for each possible value assignable to the field
        assign value to x, y
        call solve(vacant, count) recursively

    clear field

您将遇到的另一个问题，调试起来会变得相当难看，这要归功于这一行：

int possibleEntries[9];

在递归中使用和覆盖的全局变量至少可以说是一个坏主意。想象一下这样的程序可能运行（ident 表示递归级别，其中没有 ident 表示操作是全局的）：

solve
 |
 ---> board empty? Nope
      x,y <- next vacant field
possible values <- possible values for x, y
      field[x, y] <- first value from possible values
      solve
       |
       ---> board empty? Nope
            x, y <- next vacant field
possible values <- possible values for x, y (overwrites global variable!!!)
           field[x, y] <- first value from possible values
           solve
            |
            ---> ...
       <--- return
       field[x, y] <- second value from possible values (WRONG!!!)
       ...

最后一个分配不会使用为您当前正在处理的字段生成的可能值列表，而是使用您在返回之前在递归中访问过的另一个值列表。您可以通过两种方式解决此问题：

  • 从 1 到 9 迭代，分别检查每个数字是否可以分配给字段
  • 为每个递归级别保留一个单独的列表
于 2018-02-20T18:08:29.303 回答