孔明棋

大家好，我是讯享网，很高兴认识大家。

跳转原文

说明：写完才发现，文中的很多截图都被csdn打上水印，其实这些截图都来自上述原文，尊重原著！！

根据WIKI孔明棋应该起源于欧洲，原名pegged, 不知道现在怎么和诸葛亮扯上了关系。规则和跳棋相似，但是一个人就可以玩，目标是按照规则移动棋子，最终只有一个棋子留在棋盘上。发展至今，pegged已经发展出很多新的形式，但是最典型的是如下形式

讯享网

33个棋子，起始可以任意取走一个棋子，典型的第一步是取走中心的棋子，然后按规则移动棋子。现在的问题是：计算机可以玩这个游戏吗？

考虑下解空间的规模，33个棋子，最终要剩下1个棋子，一个bit表示一个位置上是否有棋子，则可能布局一共有2^32个，在64位机器的时代，这个数不算什么。考虑暴力穷举，从第一步开始就是遍历树，因为只有32个棋子，所以树的深度最大32，深度优先遍历，单纯的递归也可以处理，github上似乎已经有开源的代码了，还利用了hash做剪枝。

本文的重点是翻译开头的网页内容：用群论求解最后余下的那个棋子可能的位置
Peg Solitaire的规则很简单, Pegs可以在水平/竖直方向上跳过相邻的pegs,被跳过的Pegs被消除。

游戏的目的是消除到只剩一个pegs。在central solitaire中，玩家第一步取出的是位于中心的pegs。根据游戏说明，可以让最后一个pegs处于中心位置的人是天才，而其他可以取胜的人只能算是优秀的人。

不久以前，来自idaho大学的Arie Bialostocki利用群论证明最后取胜时，那余下的唯一的pegs只可能在五个位置（如上图的b)

例如，当最后一个pegs位于棋盘最右侧时，figure 1(c)展示的就是倒数第二个移动步骤。讽刺的是，同样是figure1(c)的状态，玩家同样可以让最后一个棋子处于中心位置，从而从“优秀”变成“天才”。有人会权衡两种结果的区别吗？就是因为这个神奇的现象引导Arie Bialostocki得到一个优雅的理论，如下所诉。

figure2(a)给棋盘上每一个位置设置一个字母x,y,z. the arrangement of letters is very special and has been noticed yet in the classic WW,page 706(译注：这一句的WW没看明白，故保留原句。这个字母的布局相当重要，至于怎么会出现如此特殊的设置，下文在另一个文献中或许有所体现，耐心看下去）处于某个字母位置上的pegs跳过另一个字母位置上的pegs总是会落在第三个字母的位置上。