围棋有几种变化是一个老问题了，比较粗浅的说法是3的19乘19次方，意思就是棋盘上每个点有空、黑、白三种状态，总共有19*19个点，所以得出这个结果。但实际上并没有那么多，因为在那么多状态中，有很大一部分是不可能出现的状态，也就是盘面上有死棋的状态。比如整个棋盘上布满棋子的状态都是不可能的，而这种状态就有2的19*19次方之多。
所以很久以前我曾经在论坛上提出过“围棋合理的变化到底有几种”的问题。我原先想从纯组合数学的角度来解决，试图得出一个简单的表达式结果来。但想了半天，也没有一种合理的思路。写个程序来计算当然是可能的，但当初论坛上似乎所有人都说这没意义。我心有不甘，最近终于借着学习java的机会写了个这么粗浅的程序(GoCount.java)。
这个程序的算法无疑是很直接和低效的，它就是对一个n*n的棋盘，枚举所有3^(n*n)种情况，对每种情况判断每个点是否都是活棋，如果每个点都是活棋，则全局是一个合理的局面。对每个点是否活的判断标准(对应isAlive函数)是一个递归：一个点存活当且仅当它是一个空点或与这个点相邻的点上有空点或同色活棋。
这个程序的效率分析如下：
enumAllStatus函数枚举所有状况，共执行3^(n*n)次。在每一次执行enumAllStatus中，要调用isValid函数（判断是当前局面是否合理），它又调用：resetVisited函数(重置每个点的访问标志)，执行n*n次； isAlive函数（判断每个点是否活），也执行n*n次。IsAlive函数又是一个递归函数，它的递归深度不太好估计，我感觉它大概会是与n线性阶的一个数。所以isAlive总共执行次数会是o(n^3)，相对于resetVistied，它起主要作用。所以整个算法的时间复杂度是o(3^(n*n)*n^3)。
我计算了一些结果，设一个n*n的棋盘，它的所有合理变化的数字用V(n)表示的话，则V(1)=1,V(2)=57, V(3)=12675,V(4)= 24318165. 在我的机器上，计算V(3)用了125ms，计算V(4)用了498907ms，约8分多钟。而如果用计算V(3)的时间和前面的时间复杂度估算计算V(4)的时间（忽略次要项和常系数），结果将是648000ms，与实际情况在同一数量级上，所以我感觉我的时间复杂度估计还是大致准确的。
但这样的话，估计计算V(5)需要的时间大约在几百天的数量级上。另一个问题是，目前我用的是int的变量来计数，java中int型最大值是2^31-1，它只能处理n=4的情况。即使改成long型，它也只能处理n=5，你可以自己算一下。当然，这是一个次要问题，算法的低效才是主要问题。
另一个有趣的思考是考察V(n)/3^(n*n)的值，也就是合理的变化占所有变化的比值。根据目前结果：
n=2: V(2)=57, 57/3^4= 0.7037
n=3: V(3)=12675, 12675/3^9= 0.6440
n=4: V(4)=24318165, 24318165/3^16=0.5649
似乎是越来越小，那它最终会不会去趋向于一个常量呢？我感觉如果乐观估计的话V(n)/3^(n*n)会趋向于一个大于0.5的值，至少也是1/3，但苦于找不出证明。我很希望谁能先给出一个它不会趋向于0的证明。
另一方面，你也可以帮我优化一下算法，但主要的优化是要使程序不必枚举3^(n*n)种变化，否则程序不会有质的改善。
本文地址：http://com.8s8s.com/it/it33747.htm