2

假设一个二维数组包含一个 9x9 数独网格，我的求解函数在哪里崩溃？我正在尝试使用简单的回溯方法来解决这个问题。谢谢！

bool solve(int grid[9][9])
{
 int i,j,k;
 bool isSolved = false;

  if(!isSolved(grid))
   isSolved = false;

  if(isSolved)
   return isSolved;

  for(i=0; i<9; i++)
  {
   for(j=0; j<9; j++)
   {
    if(grid[i][j] == 0)
    {
     for(k=1; k<=9; k++)
     {
      if(legalMove(grid,i,j,k))
      {
       grid[i][j] = k;
       isSolved = solve(grid);
       if (isSolved)
        return true;
      }
      grid[i][j] = 0;
     }
     isSolved = false;
    }
   }
  }

return isSolved;
}

即使改变了isSolved问题，我的解决方案似乎也陷入了无限循环。看起来我错过了一些基本案例步骤，但我不确定在哪里或为什么。我已经查看了类似的解决方案，但仍然无法确定问题所在。我只是想创建基本的求解器，不需要提高效率。谢谢您的帮助！

4

3 回答 3

4

是的，你的基本情况搞砸了。在递归函数中，基本情况应该在开始时处理。你得到了

bool isSolved = false;

if(!isSolved(grid))
    isSolved = false;

if(isSolved)
    return isSolved;

请注意，您的 isSolved 变量永远不能设置为 true，因此您的代码

if(isSolved)
    return isSolved;

无关紧要。

即使你解决了这个问题，它也会感觉像是一个无限循环，即使它是有限的。这是因为您的算法每次调用求解时可能总共需要检查 9*9*9 = 729 个案例。输入此函数 n 次可能需要检查多达 729^n 个案例。显然不会检查很多案例，因为它会在放置非法时找到死胡同，但是谁说可能数字的 90% 的排列导致除了一个数字之外的所有数字都合法的情况？此外，即使您要平均检查 k 个案例，其中 k 是一个小数字（k<=10），这仍然会爆炸（k^n 的运行时间。）

诀窍是“尝试”将数字放置在它们很可能成为实际良好位置的地方。可能我能想到的最简单的方法是约束满足求解器，或者具有启发式的搜索算法（如 A*。）

实际上，我基于约束满足求解器编写了一个数独求解器，它可以在不到一秒的时间内解决 100x100 的数独问题。

如果奇迹般地“蛮力”回溯算法在 9x9 情况下对您很有效，请尝试更高的值，您将很快看到运行时间的恶化。

我不是在抨击回溯算法，事实上我喜欢它，它一次又一次地表明，如果正确实施回溯可以与动态编程一样有效，但是，在您的情况下，您没有正确实施它。您正在对其进行暴力破解，您不妨让您的代码非递归，它会完成同样的事情。

于 2009-10-06T05:13:27.730 回答
3

您将isSolved称为函数和布尔变量。我不认为这是合法的，而且它绝对不聪明。

您的函数应该具有与变量不同的名称。

于 2009-10-06T04:07:37.283 回答
2

似乎无论这是否合法，您都将“0”分配给方格，即“grid[i][j] = 0;” 线。也许你的意思是把“else”然后“grid[i][j] = 0;” ?

于 2009-10-06T04:32:26.423 回答