algorithm - 回溯算法解决数独问题的时间复杂度

Question

我正在实施一种回溯算法来解决数独难题，并​​且需要对该算法进行经验分析。但是，我发现很难理解这种回溯算法解决数独难题的时间复杂度。数独板是一个 9 x 9 的网格，因此每个空格都可以取 1-9 的值，但它首先检查行、列、3x3 框以查看这样做是否安全，并且有 m 个空格。我逐行遍历网格以寻找空白区域，然后遍历数字 1-9，检查哪个数字可以安全放置。如果号码是安全的，我将它放在那里，然后再次调用我的函数（重复）以检查下一个空格等等。如果它没有导致解决方案，则算法回溯，然后将下一个数字放在该空间中并再次尝试。

我将需要生成将是回溯算法的最佳/最坏情况时间复杂度的网格。因此，为了能够做到这一点，我需要了解实现的回溯算法的时间复杂度。如果有人可以帮助向我解释它的时间复杂度以及如何计算数独回溯的最佳/最坏情况，或者如果有人可以将我与可以提供帮助的适当文档联系起来，我将非常感激。

提前致谢 ：）

标签： algorithmcomplexity-theorybacktrackingsudoku