11

我正在寻找“你是如何找到它的”，因为我不知道如何找到我的程序的算法复杂性。

我使用 java 编写了一个数独求解器，但没有考虑到效率（我想尝试让它递归地工作，我成功了！）

一些背景：

我的策略采用回溯来确定，对于给定的数独谜题，该谜题是否只有一个唯一的解决方案。所以我基本上读了一个给定的谜题，然后解决它。一旦我找到了一个解决方案，我不一定完成，需要继续探索进一步的解决方案。最后，会出现以下三种可能结果之一：拼图根本无法解决，拼图有唯一的解决方案，或者拼图有多个解决方案。

我的程序从一个文件中读取拼图坐标，该文件的每个给定数字都有一行，由行、列和数字组成。按照我自己的约定，7的左上角写成007。

执行：

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

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

任何帮助表示赞赏

4

2 回答 2

29

O( n ^ m ) 其中n是每个方块的可能性数（即经典数独中的 9 个），m是空白的空格数。

这可以通过仅从单个空白向后工作来看出。如果只有一个空白，那么在最坏的情况下，您有n 个必须解决的可能性。如果有两个空白，那么对于第一个空白的每个可能性，您必须为第一个空白处理n个可能性，为第二个空白处理n 个可能性。如果有三个空白，那么您必须为第一个空白处理n种可能性。这些可能性中的每一个都会产生一个包含两个空格的谜题，其中有n ^2 个可能性。

该算法通过可能的解决方案执行深度优先搜索。图表的每个级别代表单个正方形的选择。图的深度是需要填充的正方形的数量。在分支因子为n且深度为m的情况下，在图中找到解决方案的最坏情况性能为 O( n ^ m )。

于 2013-03-10T21:02:49.317 回答
2

在很多数独游戏中，都会有几个数字，稍微想一想就可以直接放出来。通过在第一个空单元格中放置一个数字，您放弃了很多减少可能性的机会。如果前十个空单元格有很多可能性，你就会得到指数增长。我会问这些问题：

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

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

...

数字 9 在最后一行的哪个位置？

相同但有九列？

一样，但有九个盒子？

哪个数字可以进入第一个单元格？

哪个号码可以进入第 81 格？

那是324个问题。如果任何问题只有一个答案，你就选择那个答案。如果任何问题根本没有答案，你就回溯。如果每个问题都有两个或更多答案，则选择答案数量最少的问题。

您可能会获得指数级增长，但仅限于非常困难的问题。

于 2014-03-28T22:20:34.450 回答