数独求解器的算法复杂度（Big-O）

Question

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

我写了使用Java数独解算器，没有考虑效率（我想尽量做到递归地工作，这是我成功有！）

一些背景资料：

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

我的程序从包含行，列和数字的每个给定数字有一行的文件中读取拼图坐标。根据我自己的惯例，7左上角方形写成007

实现：

我加载值，从文件，并将其存储在一个2-d阵列 我下井数组，直到找到空白（未填充的值），并将其设置为1.然后检查是否存在任何冲突（无论我输入的值是否有效）。 如果是，我将转到下一个值。 如果否，我增加值1，直到我找到一个数字的工作，或者如果他们都没有工作（1至9），我回去1步到我调整的最后一个值，我增加了一个（使用递归）。 我完成了所有81个元素的填充，没有冲突。 如果找到任何解决方案，我将它们打印到终端。 否则，如果我试图在最初修改的FIRST元素上“返回一步”，这意味着没有解决方案。

我的程序如何算法复杂？我想这可能是线性的[O（N）]，但我访问数组多次，所以我不知道:(

任何帮助表示赞赏

Answer 1

O（ñ ^米）其中ñ是可能性为每个正方形的数量（即，9个在经典数独）和米是是空格数。

这可以通过从仅单个向后工作中可以看出空白。如果只有一个空白，那么你有n您在最坏的情况下必须完成的可能性。如果有两个空格，那么您必须通过第一个空白的n的可能性和第一个空白的每个可能性的第二个空白的可能性。如果有三个空格，那么您必须通过n第一个空格的可能性。这些可能性中的每一个将产生具有两个空白的难题，其具有n^2个可能性。

该算法通过可能的解决方案执行深度优先搜索。图的每个级别代表单个正方形的选择。图的深度是需要填充的正方形的数量。随着Ñ和分支因子的米的深度，发现在曲线图中的溶液为O的最坏情况下的性能（Ñ ^米）。

Answer 2

在许多Sudokus，会有一些数字，可以放在一个有点思考的直接。通过在第一个空单元中放置一个数字，你放弃了很多机会来减少可能性。如果前十个空单元有很多可能性，你会得到指数增长。我会问这些问题：

在第一行的哪里可以打1号？

在第一行可以找到数字2吗？

...

凡在最后一行可以在9号去了？

相同但有九列？

相同，但与九个盒子？

哪个编号可以进入第一个单元格？

哪个号码可以进入第81个单元？

这就是324个问题。如果有任何问题只有一个答案，你就选择这个答案。如果有任何问题根本没有答案，那么你会回溯。如果每个问题都有两个或两个以上的答案，您可以选择一个答案最少的问题。

您可能获得指数增长，但只对真正困难的问题。