从统计物理到数独游戏

也许大家对统计物理这门学科很陌生，但是却基本玩过数独这个游戏。今天我就要来介绍一下怎么从神奇的统计物理出发来解决数独问题。

假如给你一台计算机，然后让你编个程序来解决数独问题。你会用什么思路来编程。首先我们可以用最简单的思路：利用计算的计算速度一一列举所有的可能填法，然后利用数独成功的规则来进行判断，几个循环加上一个判断条件就完成了，是不是很简单。其实这样做当然没有问题，但是就是很废时间，也没有任何美感。那么更聪明一点方法呢，我们还可以沿着人类做数独题的策略出发，由于我们事先知道规则，可以利用同一个九宫格，同一行，同一列已有的数字去排除空格不允许填的数字，这样一来我们可以跳过很多“坑”，沿着这个思路程序也可以写程序解决数独问题，而且时间大大缩小。

但是呢，我还是要说还有一个更具有美感的算法。在介绍这个算法之前，我们先介绍一下统计物理里面一个重要的模型：Potts模型。这里的Potts 模型是一个定义在晶格上的模型，其状态可以有 q 个取值，记为 1,2,3...q，其中 q 为整数。如下图中所示, 在二维正方晶格上，Potts 模型的 q 取值为 3。我们用三种不同的颜色：红色，蓝色以及绿色来代表三个不同的状态。

现在，我们给Potts模型制定一个规则：任何相邻两个颜色填充块如果颜色一样的话，我们记为二者相互作用的“能量”为1，否则能量为0。那么上图整个格子拥有的能量是多少呢，大家无妨去数一数。如果不愿意数也没关系，接着往下看就可以了。

如果我们希望整个格子的能量越低越好，也就是任何两个相邻的色块最好都不一样，这样格子拥有的总能量是不是就是0了，大家再试着想一想我们有没有办法安排这些颜色来使整个格子能量为0。聪明的你们是不是瞬间联想到一个著名的数学问题：四色问题。没错，很棒。也就是说我们的Potts模型可以等价四色问题，这是一个非常漂亮的结果。

现在我们回到数独问题，既然我们可以用Potts模型来表示四色问题，那么我们离表示数独也就不远了。想象一下，数独问题中每一个空格就是要填充的颜色，我们可以填九种颜色（图就不好画了，省略）。然后能量计算的规则便是：同一个九宫格，同一行，同一列任何两个颜色如果一样那么能量就是1，如果不一样那么能量就是0。当所有色块的颜色填充使得整个格子能量为0，那么是不是就满足了数独条件！很完美的表达。

等等，你可能会说了，你不就是找了一个所谓的Potts模型来重新定义了数独游戏的规则么。是的，我们就是用统计物理Potts模型语言来重新表述了一下而已。但是下面关键来了，统计物理中有一个很有名的蒙特卡洛（MC）算法来解决Potts问题，其名字为“模拟退火算法”。在这里我不用数学公式去解释这个算法，而用一个不那么严谨的语言稍作解释。我们引入一个温度的概念，同时将数独中任何两个能组成能量的空格之间加入一条想象的线，这条线会倾向于让连着的格子选择不同的颜色。在高温的时候，格子太热了，在不同颜色之间随意变化，牵着的线对他们影响很小。随着温度降低，线的影响力越来越大，格子颜色的选择开始听话，尽量选择不同的颜色，直到温度降为0的时候，线会强制所有相邻的格子颜色取值不一样。听上去是不是很有意思，没错，就是很有意思。值得一提的是，模拟退火算法并不能保证温度降着降着就能让数独格子最后的系统百分之百为零，里面涉及的细节也是不少的，在此就不赘述了。

上面图就是我用自己写的小程序得到的结果了，效果很棒，虽然图很丑。