数独求解器的算法复杂度（Big-O）
我正在寻找“你如何找到它”，因为我不知道如何找到我的程序的算法复杂性。
我用java编写了一个数独求解器，没有效率的想法（我想尝试让它递归工作，我成功了！）
一些背景：
我的策略采用回溯来确定，对于给定的数独谜题，谜题是否只有一个独特的解决方案。 所以我基本上阅读了一个给定的谜题并解决它。 一旦我找到了一个解决方案，我不一定完成，需要继续探索进一步的解决方案。 最后，三种可能的结果之一发生：难题根本无法解决，拼图有独特的解决方案，或者拼图有多种解决方案。
我的程序从一个文件中读取拼图坐标，该文件对于每个给定的数字有一行，包括行，列和数字。 根据我自己的惯例，7的左上方标记为007。
执行：
我从文件中加载值，并将它们存储在一个二维数组中，我沿着数组向下直到找到一个空白（未填充的值），然后将其设置为1.并检查是否有任何冲突（值是否为i输入有效或无效）。 如果是，我转到下一个值。 如果不是，我将值递增1，直到找到一个有效的数字，或者如果它们都不起作用（1到9），我返回1步到我调整的最后一个值，然后递增该值（使用递归）。 当所有81个元素都被填满时，我完成了解决，没有冲突。 如果找到任何解决方案，我将它们打印到终端。 否则，如果我尝试在我最初修改的FIRST元素上“返回一步”，则表示没有解决方案。
我的程序如何算法复杂度？ 我以为它可能是线性的[O（n）]，但我多次访问该数组，所以我不确定:(
任何帮助表示赞赏
O（ n ^ m ）其中n是每个方格的可能性数（即经典数独中的9）， m是空白的空格数。
这可以通过仅从一个空白向后工作来看出。 如果只有一个空白，那么你有可能在最坏的情况下必须完成。 如果有两个空白，则必须为第一个空白处理n种可能性，对于第一个空白的每种可能性，必须为第二个空白处理n种可能性。 如果有三个空白，那么你必须为第一个空白处理n种可能性。 这些可能性中的每一种都将产生具有两个空白的拼图，其具有n ^ 2种可能性。
该算法通过可能的解决方案执行深度优先搜索。 图表的每个级别代表单个正方形的选择。 图的深度是需要填充的方块数。 在分支因子为n且深度为m的情况下，在图中找到解决方案具有O（ n ^ m ）的最差情况性能。
在许多Sudokus中，会有一些数字可以通过一些思考直接放置。 通过在第一个空单元格中放置一个数字，您可以放弃很多机会来减少可能性。 如果前十个空单元格有很多可能性，那么就会呈指数级增长。 我问的问题是：
第一行中的数字1可以去哪里？
第一行中的数字2可以去哪里？
…
在最后一行中9号可以去哪里？
相同但有九列？
同样但有九个盒子？
哪个号码可以进入第一个单元格？
哪个号码可以进入第81个小区？
这是324个问题。 如果任何问题只有一个答案，那么你选择答案。 如果任何问题根本没有答案，那么你回溯。 如果每个问题都有两个或更多答案，则选择答案数最少的问题。
您可能会获得指数级增长，但仅适用于非常困难的问题。