Saturday, November 29, 2008

华容道之最(八)最难的严格镜像玩法

好吧,猜对了,最难的还就是小兵探路。
  • 最难严格镜影:239步
  • 最难严格倒影:283步
  • 最难严格反影:282步
以上三种都是只有小兵探路和它的变种一共两种布局。

结论很简单,但为了得出这个结论,我搜索了1,354,392,637,781个节点,3000小时左右的CPU time……我相信一定会有比暴力搜索更好更快的办法。我也相信这三个数字是对的,遗憾的是目前还没有在网上找到过其他人的结论,没法互相验证。

和镜像玩法类似的,搜索也得出了在这种严格意义下的最长的最短路径,仍然是小兵探路的这两种布局,但步数不再是任何一种镜像了。下面这张图就是其中的一种情况,从左边走到右边一共需要287步,比严格倒影和严格反影稍微多一点。


No comments: