数独求解器的算法复杂度（大O表示法）

Question

我正在寻找“如何找到算法复杂度”，因为我不知道如何确定我的程序的算法复杂度。

我使用Java编写了一个数独求解器，没有考虑效率（我想尝试使用递归来使它工作，而我成功了！）。

一些背景：

我的策略是使用回溯法来确定对于给定的数独难题是否只有一个唯一的解。所以我基本上读入一个给定的谜题并解决它。一旦我找到一个解，我不一定完成，需要继续探索更多的解。最后会有三种可能的结果：拼图根本无法解决、拼图有唯一解或者拼图有多个解。

我的程序从一个文件中读入谜题坐标，该文件每行都包含一个数字，由行、列和数字组成。按照我的约定，7的左上角方格被写成007。

实现：

我将值从文件中加载并将它们存储在一个二维数组中。 我沿着数组下移，直到我找到一个空白的（未填充的）值，并将其设置为1。并检测任何冲突（输入的值是否有效）。 如果是，我就继续下一个值。 如果不是，我将该值增加1，直到找到一个有效的数字，或者如果所有数字都不行（从1到9），我回到上一个值并将其增加1（使用递归）。 当所有的81个元素没有冲突地填满时，我完成了解决。 如果找到任何解，我会将它们打印到终端上。 否则，如果我尝试在我最初修改的第一个元素上“返回一步”，这意味着没有解。

我的程序算法复杂度是多少？我以为可能是线性[O(n)], 但是我多次访问数组，所以我不确定:(

感谢您的任何帮助。

- Eric Muller

---

如果你在使用回溯算法，那么你的复杂度很可能是指数级的。也就是说，对于每一步操作，你都会递归地尝试几乎所有其他可能的操作。 - millimoose

你能发一下你的代码吗？或者只发相关部分就好了。 - Daniel Williams

Answer 1

时间复杂度为O(n ^ m)，其中n表示每个空格的可能性数（例如经典数独中为9），m表示空格的数量。

这可以通过从仅有一个空格开始逆推得出。如果只有一个空格，那么在最坏情况下，你必须处理n种可能性。如果有两个空格，那么对于第一个空格，你必须处理n种可能性，对于第二个空格，你必须为第一个空格的每个可能性都处理n种可能性。如果有三个空格，则你必须为第一个空格处理n种可能性。每一种可能性都会产生一个具有n^2个可能性的两个空格的谜题。

该算法通过对可能的解决方案进行深度优先搜索来执行。图的每个级别代表单个方格的选择。图的深度是需要填充的方格数。由于分支因子是n，深度为m，因此在图中查找解决方案的最坏性能为O(n ^ m)。

- Matthew T. Staebler

---

在数独游戏中，由于每个数字只能使用一次，因此您第二个留空只需要尝试n-1种可能性，第三个留空只需要尝试n-2种可能性，以此类推。 - cozos

如果只有一个空格，那么只有一种可能性——缺失的数字。嗯...我的意思是，我猜你必须检查行和列以排除其他（n-1=8）个数字，这需要O(n)时间，但这些不会引起递归。 - mpen

这对于最天真的算法来说将是最坏的情况。如果使用任何基于规则的消除方法，O(n^m)将被替换为比n^2小得多的m。实际上，一个已经填入某些方格的9x9数独可能可以使用暴力规则修剪算法在非常快的时间内解决。当然，它是非线性和NP完全的，也有从这个角度解决它的方法。 - Gregory Morse

Answer 2

在许多数独游戏中，通过一些思考可以直接放置几个数字。如果在第一个空单元格中放置一个数字，则会失去许多减少可能性的机会。如果前十个空单元格有很多可能性，则会出现指数增长。我会问以下问题：

第一行中数字1可以放在哪里？

第一行中数字2可以放在哪里？

...

数字9可以放在最后一行的哪里？

九列也是一样的吗？

九个盒子也是一样的吗？

哪个数字可以放到第一个单元格中？

哪个数字可以放到第81个单元格中？

这是324个问题。如果任何问题只有一个答案，您就选择该答案。如果任何问题根本没有答案，您就要回溯。如果每个问题都有两个或更多的答案，您就选择具有最小答案数量的问题。

您可能会遇到指数增长，但仅适用于真正困难的问题。

- gnasher729

---

它将一个NP完全问题转化，只要不是一个简单的数独问题，就会出现指数级增长。除非P=NP，但这不太可能... - Gregory Morse