空当接龙的牌全都看得见,所以很适合用电脑来找解法。这里通俗地介绍电脑是怎么解空当接龙的。为了本文,我们做了一个按和应用“空当接龙”相同的规则运行的程序来试验。
搜索:走一步,再往后查
电脑和人一样,会查“走这一步,会怎么样”。不同的是数量。
- 把当前牌面上能走的步骤全部列出来(放进空闲单元、叠到牌列里、叠进目标单元等)。
- 走其中一步,生成新的牌面。
- 在这个牌面上,再把能走的步骤全部列出来。
- 找到把52张牌叠进目标单元的牌面,那么到那里为止的步骤就是答案。
这种“从一个牌面走到下一个牌面,一路分叉往下走”的做法,叫搜索。
办法1:不重复查同一个牌面
空当接龙里,按不同顺序移动,常常会走到同一个牌面。把牌往右挪,再往左放回来,就回到了原来的牌面。把查过的牌面记下来,遇到同样的牌面就不再查,浪费就会大大减少。
另外,只有列的顺序不同的牌面,以及只有空闲单元里排列顺序不同的牌面,解法也是一样的。把它们当作同一个牌面处理,能进一步减少要查的数量。
办法2:先查有希望的牌面
要是把所有的牌面按顺序都查一遍,花的时间太长了。所以要给牌面打分,比如“叠进目标单元的张数多”“接下来想叠进目标单元的牌上面压着的张数少”“空闲单元空着”,然后先查有希望的牌面。
用本文的程序解Windows空当接龙第1号牌局时,查了843个牌面,就找到了110步的解法。人来想很费劲,对电脑来说是一瞬间的事。找到的步骤,不一定是最短的(步数和过关所需的步数)。
确认解不开
找到了解法,这副牌就是能解开的。那么,“解不开”是怎么确认的呢?
答案是,把能走到的牌面全部查一遍。不管走哪一步,都不再出现新的牌面,而且其中也没有叠满52张的牌面,就能知道这副牌解不开。
Windows空当接龙的11982号,是出名的解不开的牌局。用本文的程序,11982号连同从目标单元退回牌的一步在内,把能走到的牌面(约9万5千个)全部查完,也没有解法(空当接龙几乎都能解开)。
一起移动牌的规则,和能不能解开无关
在应用“空当接龙”里,一次能移动的是“空着的空闲单元数+1”张,空列不会增加这个张数(一次能移动的张数)。但是,一起移动牌的步骤,可以拆成用空闲单元和空列一张一张移动的步骤。能走到的牌面是一样的,所以能解开的牌局相同。变的只是步数的计算方式。
应用“空当接龙”牌局的核算
应用“空当接龙”的牌局,每次都是随机洗匀发牌。作者用电脑解了随机的10万副牌,并把找到的解法,用和应用相同的游戏机制实际走到了最后来核实。结果是,10万副牌全部都有解法。
不过,这并不是“所有牌局都能解开”的证明。没查过的牌局里,仍有可能极少数是解不开的。
解法的思路,人来玩的时候也能派上用场。也请看看空当接龙的攻略和必胜法。
