孔明棋的答案,可以用电脑来找。无论是应用“孔明棋”的“提示”,还是本站确认答案的时候,用的都是思路相同的程序。这里通俗地介绍其中的原理。

依次尝试所有步骤

最直接的方法,是重复选一个能走的步骤走,再选一个能走的步骤走。走进死胡同了,就退回1步,选一个还没试过的别的步骤。

  1. 在当前局面里,选一个能走的步骤走。
  2. 球只剩一颗时,就找到了答案。
  3. 没有能走的步骤了,就退回1步,试别的步骤。
  4. 所有步骤都试完了,就再退回1步。

这种方法叫深度优先搜索。人用“撤销一步”来试的做法,电脑以快得惊人的速度重复。

不重复检查同一个局面

在孔明棋里,用不同的顺序走,也常常会变成同一个局面。英式33孔,第7步之后的走法超过22万种,但形成的局面只有2万2千种左右(解法有多少种?)。

所以,把查过一次、知道是死胡同的局面记下来,下次再遇到,就马上折返。光是这样,要查的量就大大减少。

在本站用的程序里,英式33孔从正中间开局、留在正中间的答案,一瞬间(不到0.1秒)就找到了。不过,并不总是这么快。换了第二步的棋盘,用同样的方法找,花了9秒左右。先从哪一步试起,所花的时间会有很大差别。

不往后推算就中止

另一个巧思是,一旦知道这个局面无论怎么走都够不着目标,就不再往后查,直接中止。这叫“剪枝”。

应用里,用下面两种方法来剪枝。

  • 3色涂色:把棋盘斜着涂成3种颜色,每走1步,3种颜色所有球数的奇偶都会对调。因此,从当前局面出发最后一颗球能留下的孔,光靠计算就能知道(3色涂色的文章)。
  • 王球的行和列:王球每次移动2格,所以它所在的孔的行和列的奇偶不会改变(把王球留到最后的诀窍)。

如果棋盘上同时满足两个条件的孔一个也没有了,就没有能把王球留到最后的孔。这个局面,不用往后推算,就知道“无解”。

在应用的“提示”里

应用的“提示”,会寻找从当前局面出发能够达成目标的下一步,并用金色圆圈点亮。

  • 先记住题目的答案:“题目”的棋盘是倒着跳生成的,所以知道生成时的答案(必定有解的题目是怎么生成的)。答案路线上的局面都记着“有解”,所以能马上回答。即使是偏离路线的局面,找的过程中如果汇入了答案的路线,就能在那里停下。
  • 给查找的量设上限:1次提示要查的,最多是150万个局面或3秒。棋盘大的时候,也有在那之前得不出答案的情况。
  • 告诉你退回的步数:从当前局面已经够不着目标时,或者到上限还不知道时,会查“撤销一步”能退回到的局面,像“退回3步就能留下”这样,告诉你该退回几步。因为是把能退回的局面每次减半来查的,所以即使步数多也能很快找到。

人来解的时候的提示

电脑的巧思,人来解的时候也能用。

  • 记住走进死胡同的形状:失败过一次的形状,即使用别的顺序走到,也还是会失败。
  • 从终点倒着想:最后能留下的孔,从开局起就定了。先定好想去的孔,选步骤就容易了(留到正中间的方法)。
  • 退回去试:像深度优先搜索那样,犹豫时就退回一点,试别的步骤,这是正确的做法。