我正在写一个数独解算器，并考虑一个算法来实现它。我知道回溯具有O（n^ m）的时间复杂度，其中n是每个方块的可能性数，m是空的空格数。但我无法对舞蹈环节进行准确的分析有人能解释一下是什么吗？
最佳答案
我的donald knuth设计的舞蹈链接（算法x）也是o（n^n^2）的一种更糟的情况。事实上，它比这少得多。
当我写了两个数独解算器，一个有舞步，一个没有舞步的时候，我发现了这一点。
如果引入前向检查（在尝试继续深度优先搜索（在搜索世界中也称为修剪）之前，检查以确保该数字是有效的播放，则可以节省算法的浪费时间如果这是你所做的唯一改进，那么你仍然可能遇到更糟的情况（即第一个数字是最大数字）。
跳舞链接，如果你想把它想成这样，跳舞链接是一个向前检查优先队列深度优先搜索。真正的速度来自于覆盖网格，这样你就不需要重新计算剩下的可能性（如果你实现正确的话），这将是你的数独解算器更耗时的过程。此外，您还可以设置算法来选择（点、行、列或框），尽可能减少分支大小。
以下是一些链接，它们确实帮助我制作了我的解算器：
https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf
https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html
这个问题的大O复杂度仍然是O（n*n*n），因为我们仍然是从点到点，并尝试到该点的N值。只是碰巧Ω（x），其中x是两个实现的空空间数，但是对于跳舞链接，每一步的计算时间要少得多。
看起来跳舞链接只是一个DFS实现，因为它是对于4乘4，更糟糕的情况是4*3*2*3*2*2*2*2*2*2，这是由于列启发法，我们选择覆盖网格的列，其中包含的列数最少，以防止大规模分支。