c - 我在用递归回溯算法解决 C 中的数独时遇到问题

Question

我可以解决一个简单的难题，但尝试稍微难一点的难题是不可能的；我在看什么？这是我的求解器方法：

   int solver (int x, int y)
   {
     int a, b, i, j;
     for (a=1; a<10; a++)
     {
       if (checkEverything(x, y, a))
       {
         board[x][y] = a;
         counter++;
         if (counter == 81)
         {
           return true;
         }
                     if (x == 9)

        {

          return true;

        }

        if (counter > 200 || counter < -10) {

          return false;

        }

        for (i=0; i<9; i++)

        {

          for (j=0; j<9; j++)

          {

            if (board[i][j] == 0)

            {

              if (solver(i, j))

              {

                return true;

              }   

            }

          }

        }

        counter--;      

      }

    }

    board[x][y] = 0;

    return false;

    }

我的 checkEverything 函数检查以确保给定的数字可以安全地放置在行、列和 3x3 网格中……我很迷茫，因为它似乎对我来说是正确的，但它太慢了。谢谢你的帮助！

Answer 1

您的实现需要太多额外的检查。

在为 current 找到当前有效候选时(x, y)，从棋盘的开头找到下一个未确定的位置是多余的。

您的递归函数的复杂度将是O(N*N)*O(N)*M（N 是棋盘的边长，或 9。M 是您的复杂度checkEverything）。在这个表达式中，O(N*N)是找到下一个未确定的位置，并且O(N)是从 1 开始尝试每个数字的复杂度到 N。我不知道你是如何实现checkEverything的，但一个天真的实现会是M = O(N)。这意味着总复杂度可能约为 O(N ⁴ )

优化的常见建议是：

1. 降低寻找下一个位置的复杂性O(1)。您可以对棋盘进行预处理，并将所有未确定的位置提前获取到一个列表中。

2. 降低复杂度checkEverything。它可以O(1)通过使用一些哈希表来保存已经使用的数字，每列 9 个，每行 9 个，每个子矩形 9 个。

有了这两个建议，递归的复杂性将是O(N).

如果你想要完美的表演，我建议你学习 Knuth 发明的 Dancing Links。该算法的主要思想是使用一个二维双链表来存储所有位置的所有候选者并加速寻找下一个位置和下一个候选者，删除无效的候选者并在回溯时恢复。

http://en.wikipedia.org/wiki/Dancing_Links