“最后的晚餐”棋的最少步数

sheng_jianguo

一、“最后的晚餐”棋
　　“最后的晚餐”棋起源于“独立钻石”棋, 现流行于英、美等国。 棋盘由7根横线、7根纵线及其37个交点组成（见图一(a)）。开局时，除了正中心的那个交点空着，每个交点上都放置棋子（见图一(b)）。走法：走动一子，这个棋子必须沿横线或纵线跳过另一个棋子，而跳到空位上（被它跳过的棋子算是被吃掉了，必须立即移出棋盘）；凡连跳(允许棋子转弯抹角，但不能斜跳)的都只算一步。结局为棋盘上最后只剩下十三个棋子，其中一个位于棋盘中心（代表耶稣基督），另外十二个棋子则分别位于四角（见图一(c)）。

　　玩“最后的晚餐”棋者最想知道的问题是：从开局是否能走到结局？如果能则最少需要几步呢？在解答这些问题前，先回顾一下相应的“独立钻石”棋历史。
　　关于“独立钻石”棋，有人说是三国时代孔明所发明的益智棋，失传后辗转流传至日本、欧美，成为外国普及的益智游戏。另外也有一种说法，说它真正的名字叫做十字棋，据传是一个被囚的法国贵族，在著名的巴士底监狱中为了打发时光而想出来的。后来在十八世纪末期传至英国，才渐渐流行至世界各地。
　　“独立钻石”棋的棋盘（为了与“最后的晚餐”棋相比较，交点编号同“最后的晚餐”棋）、开局、结局见图二，下棋规则同“最后的晚餐”棋。

　　关于“独立钻石”棋的求解思路与方法不在此一一介绍，以下仅给出求解“独立钻石”棋的最佳结果。
　　1912年，柏格荷特（Ernest Bergholt）最先给出了非凡的18步解法，具体解法如下（交点编号见图二）：
(1) 6==>19
(2) 10==>12
(3) 1==>11
(4) 18==>5
(5) 31==>18
(6) 23==>25
(7) 26==>24
(8) 9==>23==>25
(9) 13==>11
(10) 15==>13
(11) 28==>26==>24==>10==>12==>14
(12) 3==>1==>11==>25
(13) 37==>27
(14) 20==>33
(15) 35==>37==>27
(16) 29==>15==>13
(17) 7==>20==>33==>31==>18==>20
(18) 21==>19
　　1964年，剑桥大学的比斯尼(J. D. Beasley) 利用一些数学技巧，证明了“独立钻石”棋不可能少于18步完成，因此柏格荷特所作出的18步是“独立钻石”棋最少步数的解法。
　　1986年，在上海举行的“独立钻石”棋征解赛中，中国女工万萍萍找到另一种不同于柏格荷特的18步“天才”解法，具体解法如下（交点编号见图二）：
(1) 6==>19
(2) 10==>12
(3) 1==>11
(4) 18==>5
(5) 31==>18
(6) 23==>25
(7) 13==>11
(8) 15==>13
(9) 26==>24==>10==>12==>14
(10) 29==>15==>13
(11) 3==>1==>11==>25
(12) 28==>26==>24
(13) 37==>27
(14) 20==>33
(15) 35==>37==>27
(16) 9==>23==>25
(17) 7==>20==>33==>31==>18==>20
(18) 21==>19
　　后来上海计算机研究所开动了大型的计算机，希望找出“独立钻石”棋18步的各种解法，结果得出令人惊异的答案：“独立钻石” 棋18步解法（同构及仅先后次序不同的解法算同一种解法）只有两种，一种是柏格荷特的，另一种便是万萍萍的！
　　　　　　　　　　　　　《待续１》

sheng_jianguo

二、“最后的晚餐”棋的15步解法
　　通过仔细分析，可以得出“最后的晚餐”棋是有解的。但能找到15步解法是很困难的。据查到的资料，上海救捞局职工培训学校的朱方付在1989年最先给出了15步解法，其中难能可贵的是第9步的连跳5次，具体解法如下（交点编号见图一）：
(1) 32==>19
(2) 12==>26
(3) 10==>12
(4) 6==>19==>32
(5) 14==>12
(6) 24==>26
(7) 32==>19
(8) 28==>26
(9) 1==>11==>25==>27==>13==>11
(10) 3==>1
(11) 22==>20
(12) 37==>27==>13==>3
(13) 35==>37
(14) 16==>18
(15) 11==>25==>35
　　是否存在少于15步的解法呢？在下一节中将分析这个问题。
　　　　　　　　　　　《待续2》

sheng_jianguo

三、“最后的晚餐”棋不可能有少于15步解法的证明
　　要证明“最后的晚餐”棋不可能有少于15步解法初看好像不难，只要将所有少于15步的走法都计算一遍，检查是否有结局就可以了。但由于所有少于15步走法约有1千万亿个，而现在一般的计算机每小时能计算处理约10亿个“最后的晚餐”棋的棋局，一台计算机至少连续不断计算100年时间才能得出结论，所以这样直接计算来证明“最后的晚餐”棋不可能有少于15步解法是不现实的。
　　为了用计算机证明这个问题，本人采用以下两个方法大大减少了 “最后的晚餐”棋的棋局计算：
1.同构法
　　在给出同构法之前，先给出“最后的晚餐”棋中的几个定义：
　　按“最后的晚餐”棋规则走完k（k≥0）步后的图形称为棋局，一个棋局可以用一组有序数列（a1，a2，a3，···，a37）表示，其中当交点编号i上有子时ai=1；反之当交点编号i上无子时ai=0。
令Gp={T，T²，T³，T⁴，S，ST，ST²，ST³}，其中T为将棋局绕中心（交点编号19）逆时针旋转90°（交点编号位置不变化）的变换，S为将棋局绕水平中心线（通过交点编号2、36）旋转180°（交点编号位置不变化）的变换。
　　可以证明，Gp构成棋局变换的对称群。
　　棋局P与棋局Q称为同构棋局，如果存在g∈Gp，使得P在g的作用下为Q，即g(P)=Q。
　　举个例子来形象化说明同构棋局（参见图三），若棋局P0为：
P0=(1,1,1,1,1,0,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)
则与其同构的8个棋局分别为：
P1=(1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)
P2=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1,1,1,1,1)
P3=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1)
P4=(1,1,1,1,1,0,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)
P5=(1,1,1,1,1,0,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)
P6=(1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)
P7=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,0,1,1,1,1,1)
P8=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1)

　　由同构棋局的定义及Gp是群，容易证明同构棋局有以下两条性质：
　　1）若棋局P与棋局Q为同构棋局，则棋局Q与棋局P也为同构棋局。
　　2）若棋局P与棋局Q为同构棋局，棋局Q与棋局R为同构棋局，则棋局P与棋局R为同构棋局。
　　由以上两条性质可以推出：若棋局P与棋局Q为同构棋局，且P再走j步不可能到结局，则Q再走j步也不可能到结局。
　　同构法的过程如下：
　　a）在每走一步后的所有棋局中，检查是否有同构棋局，如果有同构棋局，则去掉其中的一个棋局，反复这个过程，直到保留下的都是互不同构的棋局。
　　b）仅在保留下的互不同构的棋局中再可走下一步。
　　表一给出了第1步到第7步用同构法与不用同构法的走法个数。同构法在实际计算中只用到第7步，因为当大于7步时，内存需要量太大并且计算时间很长，这时再用同构法已没有多大意义了。
　　用归纳法可以证明，任意一个走完7步后的棋局总与一个用同构法保留下的棋局为同构棋局。所以采用同构法后，“最后的晚餐”棋不可能有少于15步解法可归结为29627个棋局走7步中是否有结局问题。

2.数子法
　　在给出数子法之前，先给出“可行”棋局的定义：
　　“最后的晚餐”棋的某一棋局称为“可行”棋局，如果满足以下三个条件：
　　1）如棋局中共有n个子，则n＞12，当n=13时必为结局。
　　2）如棋局为走第j步过程中的棋局，其中在结局中有子的交点处共有m个子，则j-m＜3。
　　3）如棋局为走完第j步的棋局，其中在结局中有子的交点处共有m个子，则j-m＜2。
　　不难证明，如果“最后的晚餐”棋存在少于15步解法，则解法中的每一步的棋局都是“可行”棋局。
　　数子法的过程如下：
　　a）对于“可行”棋局可以继续走下一步。
　　b）对于非“可行”棋局不再走下一步。
　　以上是用计算机证明“最后的晚餐”棋最少步数的思路，按此方法本人编制了相应计算程序，在三台普通个人计算机上共耗费约100小时，完成了约4000亿个逻辑判断，最后终于得出：在程序计算中，少于15步的所有走法中没有出现结局，再根据“同构”棋局及“可行”棋局的性质就可得出“最后的晚餐”棋不存在少于15步解法。
　　在计算证明中还得出了对“最后的晚餐”棋感兴趣者想知道的结论：
　　在“最后的晚餐”棋的“可行”棋局中，一步最多有138种不同走法；一步中最多可以连跳9次。
　　以上证明的计算正确性是在计算程序和计算过程没有错误的前提下得出的，对此感兴趣者也可自行编程来验证这个问题。但至少说明了用这种方法证明“最后的晚餐”棋不可能有少于15步的解法是可行的。
　　　　　　　　　　　　　《待续3》

sheng_jianguo

四、“最后的晚餐”棋最少步数证明与“四色问题”证明的比较
　　前面给出了“最后的晚餐”棋最少步数的一种证明方法。令人感到惊奇的是，此证明与另一个著名的“四色问题”（在为一平面或一球面的地图着色时，假定每一个国家在地图上是一个连通域，并且有相邻边界线的两个国家必须用不同的颜色，问是否只要四种颜色就可完成着色。1976年，美国伊利诺斯大学的两位数学家阿佩尔（K. Apple）和哈肯（W. Haken）成功地用计算机证明了这个问题）的证明有许多相似可比之处（其中将“最后的晚餐”棋最少步数问题简称为“15步问题”）：
1.证明类型
“四色问题”：编程计算证明（非书面理论推导证明）
“15步问题”：编程计算证明（非书面理论推导证明）
2.证明方法
“四色问题”：构形、放电法，归结为1936个构形图是否为可约的并组成不可免完备集
“15步问题”：同构、数子法，归结为29627个棋局走7步中是否有结局
3.逻辑判断
“四色问题”：≈200亿个
“15步问题”：≈4000亿个
4.证明工具
“四色问题”：三台大型计算机（IBM360）
“15步问题”：三台个人计算机（AT/COMPATIBLE：CPU～1.7GHz）
5.计算耗时
“四色问题”：≈1200小时
“15步问题”：≈100小时
6.完成日期
“四色问题”：1976年6月
“15步问题”：2006年6月

　　　　　　　IBM360计算机

　　从以上比较可以看出：30年间，基于计算机的运算能力迅速提高，“最后的晚餐”棋最少步数问题才有可能得到解决。相信不远的将来，随着计算机的运算能力进一步提高，一些悬而未决的数学难题将被一一破解。

五、结束语
　　益智游戏通常含有丰富的数学内涵，“最后的晚餐”棋是其中的一种，其规则简单，玩起来容易，适合于亲子之间的交流，真正是老少咸宜。更有趣的是，虽然“最后的晚餐”棋问题已基本解决，但它仍然可以当作一个稍具深度的数学问题来思考，比如如何寻找不同构的15步解法及不可能有少于15步解法的简捷明快的书面证明方法等等有意思的数学问题。

shshsh_0510

学习一下

litaoye

感觉独立钻石棋的同构证明不属于数学方法，基本上靠计算机枚举，而且前面提到的1千万亿种走法也有唬人的嫌疑，其实使用双向搜+同构判断，求解应该不是很难（基本上水平可以的程序员就能搞定），相比四色定理的证明，应该不是一个量级的。

sheng_jianguo

学习一下
shshsh_0510 发表于 2009-6-6 20:55

谢谢shshsh_0510 关注本贴！

mathe

写程序完成这样的问题还是可以值得鼓励一下.
但是这个问题同四色问题当然完全不具有可比性.
同样一个问题采用不同的方法会有不同的计算复杂度,其最大却别在于数学方法,其实是算法,再次才是结果的时间/空间复杂度.而四色问题的解决虽然使用了计算机,但主要的还在于数学方法.
如果你拿魔方的最小步数问题来比较倒是有一定的可比性.不够魔方要更加复杂.
而且的确如litaoye所说,采用双向搜索通常应该更好一些,上面方法应该还可以改善.

sheng_jianguo

感觉独立钻石棋的同构证明不属于数学方法，基本上靠计算机枚举，而且前面提到的1千万亿种走法也有唬人的嫌疑，其实使用双向搜+同构判断，求解应该不是很难（基本上水平可以的程序员就能搞定），相比四色定理的证明， ...
litaoye 发表于 2009-6-11 21:59

发贴后一直较忙没时间上网，今很高兴看到您的回复。
谢谢您提出的想法。我想你可能误会我的意思了，我想说的是我的证明与“四色问题”证明有许多相似可比之处，不是说这两个问题在各方面是等价的。1千万亿种走法是我推算出来的（各种可能走法，不管同构不同构），当然是无法证明的（否则就不需编程证明这个问题了）。4000亿个逻辑判断是我的程序中计数器累加得出的，当然如果编程的方法更好些，是用不到那么多逻辑判断的（当时只考虑结果没注重编程技巧）。
在阿佩尔和哈肯成功地用计算机证明了“四色问题”后20年，有人简化了编程方法（主要将1936个构形归纳为633个）后重新计算,由于大大减少了逻辑判断，较快（听说计算时间不到1小时）证明了“四色问题”，但不能由此说明原来的证明有问题或没意义，也不能说“四色问题”变成另一个简单问题了。
由于“独立钻石”棋不可能少于18步完成有理论推导证明，我开始认为“最后的晚餐”棋最少步数问题的理论推导证明应该不成问题，但通过种种努力都没成功（虽然我是学纯数学的）。
对于双向搜索，我也尝试过，但反向搜索棋局数增长速度过快（还不如文中数子法），且双向搜索不能同时采用同构法，故放弃使用。不知你说的双向搜索是什么意思？
我在这里发文另一个主要目的是，希望有编程高手有兴趣关注这个问题。如果有人也用编程方法（或其它方法）正确证明“最后的晚餐”棋最少步数问题，且其中所有计算程序在普通个人电脑上运行时间不超过1小时，我将给予重奖，说到做到，绝不食言。

数学星空

我觉得这应该有可能将此问题大大简化,毕竟是平面的组合计数问题,而魔方则是空间组合计数且每步都有很强的相关性,我也同意mathe的说法....