孔明棋的由来

孔明棋，是黑白棋的一种。唯一一种一个人就可以玩的棋子。是法国跳棋独立钻石在中国的别称，也有人叫它跳弹珠，或者叫它“Pegged”。是一种一个人就可以玩的游戏，它是由三十三个棋子排成井字型盘面，一般流传的玩法是先取去中央的那个棋子，便可以展开游戏。

游戏时，是将棋子跳过邻近的棋子，到达一个旁边空着的位置，被跳过的棋子则从棋盘上取开；跳的路径可以前、后、左、右，但不可对角跳，直到剩下最后的一颗棋子，游戏便结束了。这是一种流传很广的益智游戏，也有很多种变形的棋盘摆法。

来历

关于孔明棋的流传，有许多的传说，有人说是三国时代孔明所发明的益智棋，失传后辗转流传至日本、欧美，成为外国普及的益智游戏。另外也有一种说法，说它真正的名字叫做十字棋，据传是发明于法国，是一个被囚的法国贵族，在狱中为了打发时光，而想出来的。后来在18世纪末期传至英国，才渐渐流行至世界各地。

这种游戏的魅力在于，玩法非常简单，但是其中变化却是数不尽的，解法更是不只一种，所以不论其形式如何变化，总是能带给人们无穷的乐趣。

由于其它种排法都是孔明棋的变形，所以我们在研究的时候，就专注于孔明棋上面，并推广孔明棋的问题，想找出是否任意空一格，而不只是研究空在中央的时候，因为若只是空在中央那一格，用暴力法也可以很快找到答案，但是当我们把问题推广之后，便需要应用一些演算方法，才能够解决，也希望借由问题的推广，让这个演算法能够适用更多任何类似棋类问题的解决。

人机下棋

基本上人类在玩这类游戏的时候，多半是依据直觉，或者依据着经验法则，会有一些策略来决定如何下棋，例如有人会决定要把棋子都尽量的往中间跳，也有人会依照着自己的喜好顺序来跳，不论如何，大多是以随机的方式来决定如何走下一步的。

但是当用电脑来处理这种问题时，就不会用这种随机的方式来作，而是会以更有系统的方法找出可能的下一步，然后尝试着走过这些可能的路径，去找到最后的解答，由于电脑可以准确并大量记忆的特性，所以我们可以让电脑记忆走过的路径，所以，当电脑走到无法再走下去的情况时，可以退回到之前的盘面，改下另一种可能的走法，而继续尝试找出解答来。当然，电脑在选择可能的下一步时，也可以有一些策略来判断，要尝试哪一步才可以比较快找到解答。

由于孔明棋的盘面有33格，每一格可分为有棋子和没有棋子二种可能，因此，所有可能的盘面组合，高达2^33，相当于有80亿种以上的盘面组合，由此可以想见其盘面变化之多。所以，要是只用暴力法去展开这整个树来求解，而每走一步会少一颗棋子，总共32颗棋子需要31步才能求得解答，也就是说，这棵树最深会到31层，每一层又可能会有很多条分枝，由此可以想见这棵树的庞大。当然，这树中间是有很多重复的节点，是表示同样的盘面，所以，我们努力的方向就是在于要如何减少经过这些重复的节点，来减少搜寻的空间与时间。

假设每一种盘面用一个bit来表示，那2^33种盘面组合就得用2^33bits，相当于1GB的空间来纪录。因此在应用上我们使用了硬碟来记录走过并且确定展开下去会无解的盘面，而利用Hashing的方法，把每个盘面对应到一个bit，但是，因为硬碟大量的读写动作，所以造成在执行时的速度变慢。为了解决这个问题我们应用了一些策略。

同时，因为它有对称关系，所以我们每一种盘面，经过旋转和翻转的组合，相当于有八种盘面，因此，我们每经过一个盘面，相当于经过了八个盘面。同样的道理，在解各种盘面的时候，也可以应用这种对称的关系，来减少需要解的盘面。