智力遊戲華容道之「最強的堡壘群」 - 华容道

　　半瓶墨水兄近日又更新了他的華容道遊戲平台，遊戲關卡從先前的57個一舉增至75個（57175，竟然是回文關係）。相信是他近期以電腦程式窮竭搜索研究華容道遊戲的最新成果。這新增的十八個佈局，陣勢的佈置很多都頗奇巧，至於舊日紙上文獻裡所記載的各類別的最難解佈局，紀錄都全被打破了。

　　按半瓶墨水兄那些關卡的編號來說，各類別的最難陣勢如下：

類別 關卡編號及名字 曹出最優解步數 倒影最優解步數

無橫 63單兵種的沒落 19 無解（鏡影需54步）

一橫 64欲罷不能 93 無解（鏡影需93步）

二橫 55峰迴路轉 138 229

三橫 61小兵探路 135 262

四橫 65橫行之將 97 151

五橫 60五橫最難之局 56 98

半瓶墨水兄既然是以電腦程式作窮竭式搜索，因此筆者很相信這批最難的華容道佈局，也就是最強的堡壘群，（以曹出玩法而言）其最優解步數的紀錄是不會被刷新的。

　　在這十八個陣勢裡，筆者也見到一些有趣的東西。比如編號58的陣勢，玩曹出最少27步就成，但要是玩倒影的話，最少卻要143步，二者的倍數關係達五倍多，是筆者所見過的最大倍數關係（這是以半瓶墨水兄提供的網上求解程式尋得的結果，但實際上這一局曹出只需15步，不知該程式出了甚麼問題呢）。此外，也終於見到一些反影玩法的最優解的步數比倒影少的案例，如編號59、67這兩局，其倒影玩法的最優解步數都比反影的多一步。但一般而言，反影的最優解步數總是比倒影的多！其中編號69的一局，倒影的最優解步數只用72步，可是反影的最優解步數竟需149步，是前者的兩倍多。

　　從上表可以看到，原來編號55的「峰迴路轉」倒影最優解229步還不是最長的步數，三橫局的那個「小兵探路」，倒影之最優解需262步，成為最新的高峰！不知道這一局的嚴格倒影和嚴格反影的玩法的最優解又各需多少步，相信都不會少於270步吧！有機會要請教一下Leo Jay大俠或半瓶墨水兄了。

多谢指出，这是求解程序的一个小bug（只在曹操位于左上角且第一步就可移动的情况下出现）
我已经修正了，新的版本是15步没错。这个bug不影响完全遍历求解的结果

得到網友Leo Jay大兄的義助，分別求出了《小兵探路》三種嚴格影像的最優解。數據如下：
　　鏡影117步　　嚴格鏡影239步
　　倒影262步　　嚴格倒影283步
　　反影268步　　嚴格反影282步

待過些日子詳細整理好數據後，會給大家介紹這批最優解的具體移法的。

　

黄志华前辈：
      请教，你的嚴格鏡影，嚴格倒影，嚴格反影，怎样定义？与一般说的鏡影，倒影，反影有没有区别。
      如果没有区别，那么鏡影与正影的最佳步数是一样的。而反影可以看做为是到影的镜影，也可以看做为是另一种开局。而在所有开局中最佳步数最多的为 138步。因此走出 283步好像是不可能的。如非是别种玩法。
      我最近用程序搜索了华容道所有的开局式，我称为华容道的场景，有338700个场景，不包括大方块在出口的场景，其中有330个场景是对称场景，其余一分为二，一半是另一半的镜像。我也搜索了华容道所有场景的最佳步数，得到结果步数最多的是138步，在二横开局中，有 3种类似的开局式。
我还定义了一个“难度指数”，即为了得到最佳步数而搜索量很大的开局式。结果难度指数最大的是二横开局：22002244334411213321， 80 步， 21910 个搜索场景。
                                                      自然牛 2009年2月10日

回自然牛：很高興又見到一位編程高手來研究華容道遊戲，有關那幾種嚴格影像局的定義，可參見下面的文帖：
http://blog.chinaunix.net/u/14418/showart_1673591.html
此外，在下於這個網誌裡有關華容道的其他文章，可從下列的 tag 取得：
http://blog.chinaunix.net/tag.php?q=%C8A%C8%DD%B5%C0

祝你的研究有新的突破！

ps 要是有空，期望能幫助在下解決一些華容道遊戲方面的疑難。

　

黄志华前辈：
      看了你的回贴，很高兴，編程高手谈不上，向前辈学习。
     研究了你的文贴，我明白了，嚴格鏡影就是，以鏡影为结局目标的华容道游戏，与以出口为结局目标的华容道游戏不同，它不需要出口。谢谢！
     我要在程序上试试看了。不过程序的内存一定会加大许多。
     另外“華容道遊戲方面的疑難”，希望前辈指点一些方向，出一些课题，感激。
                                                 自然牛2009年2月11日

回自然牛：自問是電腦盲，近半年來是有幸得各方編程高手襄助，才得以一窺華容道遊戲在解法上的堂奧。在華容道遊戲上，待解決的問題還不少。或者這裡先選一個應該較易處理的問題，請閣下幫忙解決。

請先看下面的文帖：
http://blog.chinaunix.net/u/14418/showart_1767982.html

文帖裡那三個嚴格影像局都是網友Guoyang尋覓得的局例，不過之後再不見他的蹤影，如果你有空，請幫忙用程式搜索出這三個局的最優解的具體走法。

此外，在這個文帖的留言裡，在下也記下了一種特別玩法：在嚴格指定位置的玩法之中，在五橫陣勢裡，僅需對調好兩員錯了位置的大將。
這種玩法，在下希望有一個具體的最優解走法的例子。
在下想用的局例是該文帖裡的「嚴格倒影」，在右邊（紅字）的局面裡，假設是馬超和黃忠錯了位，要把這二員大將調回正確位置，最優解是多少步？具體步法怎麼走？

有勞閣下了。謝謝！

又，Guoyang網友在下面的blog中寫了十篇有關華容道研究的筆記，相信閣下也很有興趣看看的：
http://yegycy.blogspot.com/

此外，如果是容量不小的文檔，可以寄到我的電子郵箱：
mou_wa_jai@yahoo.com.hk

　