N×N棋盘骑士最短路径回溯解法无限循环问题排查

你遇到的不是无限循环，而是暴力回溯的时间复杂度过高导致运行时间极长，看起来像卡住了，核心问题有两个：

• 指数级时间复杂度无剪枝：当前代码是枚举所有合法的骑士移动路径，时间复杂度为O(8^k)，k为路径长度。且你在回溯时会清空当前节点的访问标记，会导致大量重复路径被反复搜索。n=4的场景因为棋盘极小、搜索空间有限才能快速返回，n=6时搜索空间呈指数级膨胀，自然会长时间无响应。
• 无最优解提前终止机制：就算代码已经搜到了步数为3的最优解，也不会提前终止，还是会遍历完所有可能的路径才返回最小值，进一步拉长了运行时间。

• 若要继续使用回溯实现，可以新增一个全局变量存储当前已经找到的最小步数，每次进入递归时先判断：如果当前步数已经大于等于这个最小步数，直接返回无穷大终止当前分支的搜索，能剪掉大量无效路径，大幅提升运行效率。
• 更适合这类最短路径问题的解法是BFS（广度优先搜索），BFS按步数逐层遍历节点，第一次触达目标节点时的步数就是最少步数，不会产生无意义的冗余搜索，运行效率远高于暴力回溯。

内容的提问来源于stack exchange，提问作者Pranav M