如何用最简短的二进制代码表示一张19*19的围棋棋盘的情况？ 第1页

题目是：如何用最简短的二进制代码表示一张19*19的围棋棋盘的情况？

然后问题描述中给出了一种最蠢的办法……

这真是让人哭笑不得………………

好吧，还是回归问题，如何用最简短的代码标识一个围棋棋盘情况？

事实上，稍加分析就能看出来：围棋的棋盘分为三个阶段：

布局、中盘、官子。

布局阶段棋盘上的棋子非常少，空位非常多。此时，采用坐标描述棋子是最合适的，且布局阶段黑白棋子数量相等（布局阶段几乎不可能吃子），所以可以直接按顺序储存黑白棋子坐标，譬如说：

黑子坐标，白子坐标，黑子坐标，白子坐标。

也就是说第一个坐标一定是黑子，第二个一定是白子，第三个一定是黑子，类推。

如果真的出现了吃子的情况，再采用空子坐标来修正，譬如说白子被吃掉了一个：

黑子坐标，白子坐标，黑子坐标，空子坐标、黑子坐标。

当然，我们也可以约定只要出现吃子，就不判定局面为布局，局面怎么判定以后再聊。

又由于布局阶段几乎不可能在中腹落子和顶边落子，所以可以采用变长编码。其中2、3、4和16、17、18采用短编码，即：000=2，001=3，010=4，100=16，101=17，110=18。

注意到011和111没有用，这是因为它们用于长编码：

然后：

01100=1，01101=5，01110=6，0111100=7，0111101=8，0111110=9，0111111=10

11100=19，11101=15，11110=14，1111100=13，1111101=12，1111110=11，

1111111=空子坐标

或者我们可以采用另一种长编码：

011000=1，011001=5，011010=6，011100=7，011101=8，011110=9，011111=10

111000=19，111001=15，111010=14，111100=13，111101=12，111110=11，

其实效果会差不多。

所以，如果黑子第一着在左上点三三，白子紧接着在右下点三三，记录下来就是：

001001101101

是不是很简短？

这种方式记录的一个子坐标长度平均会在8位左右，大约二十着或者更早的时候的时候编码变得不实用，因为长度已经太长，此时更换为下面的方式：

先把整个棋盘映射成一个二进制空间，规模是19*19=361位。接下来把棋子出现的位置置为1，其余为0。然后再将连续的0进行压缩编码。再用另一个二进制序列来标注出现在指定顺序位置的棋子是黑还是白。

在棋子远少于空位的中盘易得这种方式比纯粹的三进制要省空间。

先这样，有空再补充官子的记录方式……