回溯算法解数独问题的一种思路

核⼼思路，就是对每⼀个空着的格⼦穷举 1 到 9，如果遇到不合法的数字（在同⼀⾏或同⼀列或同⼀个 3×3 的区域中存在相同的数字）则跳过，如果找到⼀个合法的数字，则继续穷举下⼀个空格⼦。

对于数独游戏，也许我们还会有另⼀个误区：就是下意识地认为如果给定的数字越少那么这个局⾯的难度就越⼤。这个结论对⼈来说应该没⽑病，但对于计算机⽽⾔，给的数字越少，反⽽穷举的步数就越少，得到答案的速度越快。

为什么有时候算法执⾏的次数多，有时候少？为什么对于计算机⽽⾔，确定的数字越少，反⽽算出答案的速度越快？我们已经实现了⼀遍算法，掌握了其原理，回溯就是从 1 开始对每个格⼦穷举，最后只要试出⼀个可⾏解，就会⽴即停⽌后续的递归穷举。所以暴⼒试出答案的次数和随机⽣成的棋盘关系很⼤，这个是说不准的。那么你可能问，既然运⾏次数说不准，那么这个算法的时间复杂度是多少呢？

回溯算法最佳实践：解数独对于这种时间复杂度的计算，我们只能给出⼀个最坏情况，也就是O(9^M)，其中 M 是棋盘中空着的格⼦数量。你想嘛，对每个空格⼦穷举 9个数，结果就是指数级的。这个复杂度⾮常⾼，但稍作思考就能发现，实际上我们并没有真的对每个空格都穷举 9 次，有的数字会跳过，有的数字根本就没有穷举，因为当我们找到⼀个可⾏解的时候就⽴即结束了，后续的递归都没有展开。

这个 O(9^M) 的复杂度实际上是完全穷举，或者说是找到所有可⾏解的时间复杂度。如果给定的数字越少，相当于给出的约束条件越少，对于计算机这种穷举策略来说，是更容易进⾏下去，⽽不容易⾛回头路进⾏回溯的，所以说如果仅仅找出⼀个可⾏解，这种情况下穷举的速度反⽽⽐较快。