我正在寻找“你如何找到它”，因为我不知道如何找到我的程序的算法复杂性。
我用 java 写了一个数独求解器，没有考虑效率(我想尝试让它递归工作，我成功了!)
一些背景:
我的策略采用回溯来确定，对于给定的数独谜题，该谜题是否只有一个唯一的解决方案。所以我基本上读了一个给定的谜题，然后解决它。一旦找到一种解决方案，我不一定完成，需要继续探索进一步的解决方案。最后，会出现以下三种可能结果之一:谜题根本无法解决、谜题有唯一解或谜题有多种解法。
我的程序从一个文件中读取拼图坐标，该文件中每个给定的数字都有一行，由行、列和数字组成。按照我自己的习惯，7的左上角写成007。
实现:
我从文件中加载值，并将它们存储在二维数组中 我沿着数组向下走，直到找到一个空白(未填充的值)，并将其设置为 1。并检查是否存在任何冲突(我输入的值是否有效)。 如果是，我将转到下一个值。 如果不是，我将值增加 1，直到找到一个有效的数字，或者如果它们都无效(1 到 9)，我返回 1 步到我调整的最后一个值并增加那个值(使用递归). 当所有 81 个元素都已填满且没有冲突时，我就完成了求解。 如果找到任何解决方案，我将它们打印到终端。 否则，如果我尝试在最初修改的 FIRST 元素上“返回一步”，则意味着没有解决方案。
我的程序算法复杂度如何？我认为它可能是线性的 [O(n)]，但我多次访问数组，所以我不确定 :(
感谢任何帮助
最佳答案
O(n ^ m) 其中 n 是每个正方形的可能性数(即经典数独中的 9)和 < em>m 是空格的数量。
这可以通过仅从一个空白向后计算看出。如果只有一个空白，那么在最坏的情况下，您必须解决 n 种可能性。如果有两个空格，那么您必须为第一个空格计算 n 种可能性，为第一个空格的每种可能性计算第二个空格的 n 种可能性。如果有三个空格，那么您必须为第一个空格解决 n 种可能性。这些可能性中的每一种都会产生一个包含两个空格的谜题，其中有 n^2 种可能性。
该算法对可能的解决方案执行深度优先搜索。图表的每个级别代表单个方 block 的选择。图的深度是需要填充的方 block 的数量。使用 n 的分支因子和 m 的深度，在图中找到解决方案的最坏情况性能为 O(n ^ m)。
关于java - 数独求解器的算法复杂度 (Big-O)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15327376/