仅利用30行Python代码来展示X算法

假如你对数独解法感兴趣，你可能听说过这儿有个Python写的例子。然而，舞蹈链实现起来可能相当繁琐，并且不易写地正确。接下来就是展示Python奇迹的时刻了！有天我决定用Python来编写X 算法，并且我想出了一个有趣的舞蹈链变种。主要的思路是使用字典来代替双向链表来表示矩阵。从它那我们能快速的访问每行的列元素。为实现这个目的，我们把X转换为字典。在上述的例子中，它应该写为眼尖的读者能注意到这跟Y的表示有轻微的不同。另一方面，高德纳没有提到这点，实际上整个算法中所有行是保持不变的。平均情况下它的性能会好很多，因为它不需要遍历所有的空格位。在数独的例子中，矩阵中每行恰好有 4 个条目，无论大小，因此它有N^3的复杂度。