在应用“孔明棋”的“题目”模式里,每点一次“新游戏”,就会生成形状不同的棋盘。尽管如此,每个棋盘都一定有解。本文介绍其中的原理。
普通地生成,不知道有没有解
如果随便决定孔的形状和球的摆法,就会产生很多无解的棋盘。要确认有没有解,得查遍所有步骤,球多了会很花时间。
所以应用采用了从答案倒着生成题目的方法。
倒着跳
孔明棋的一步,是“一颗球跳过相邻的球,落到空孔里,并吃掉被跳过的球”。把它变成倒过来,就成了
一颗球回到前方隔一格的空孔,并在中间的空孔里放一颗球
这样的动作。倒着走的每一步,球都会增加一颗。
从一颗王球开始
从只剩一颗王球的棋盘(也就是过关后的棋盘)开始,叠加倒着走的步骤。用小例子看一看。
首先是只有王球的棋盘。
第1次:把王球往上退回2格,在中间放一颗球。
第2次:把中间放的球往左退回2格,在它们中间放一颗球。
第3次:把王球往右退回2格,在中间放一颗球。
这样,就做出了有4颗球的题目。
倒着走过的步骤,就是答案
把生成时的步骤,从最后一步起依次,按正常的方向走,就直接成了答案。上面的例子里,只把用到的孔当作棋盘的孔,做成题目的棋盘,就能像下面这样解开。
- 第 1 步 e1→c1
- 第 2 步 a2→c2
- 第 3 步 c1→c3
- 第 3 步之后 剩余 1 颗
倒着生成的步骤,本来就是从过关的棋盘出发的,所以按正常的方向走,一定只会留下王球。因此能保证每道题至少有一个答案。
应用里的巧思
应用在这种生成方法上,加了几个巧思。
- 重复使用孔:选择倒着走的步骤时,更容易选到再次使用已经用过的孔的步骤。这样步骤会相互交织,不容易变成只是一条直线排开的题目。
- 调整棋盘形状:生成好的棋盘,其中一半会加上孔,变成左右对称的形状。其余的,在棋盘边缘加上1到2个空孔来改变形状。加了空孔,原来的答案仍然可以走,所以有解这一点不会变。
- 同一个种子生成同一道题:题目是由叫“种子”的数生成的,所以同一个种子和难度,在 iPhone 和 Android 上会生成同一道题。
调查难度,不合适就重新生成
倒着生成的题目,一定有答案。但光是这样,可能太简单,也可能太难。
所以应用会针对生成的题目,调查答案步骤的中途,有多少步走了就再也留不下王球(陷阱步)。反复重新生成,最多24次,直到陷阱步的比例进入★1到★5各自的范围(范围见难度的文章)。
即使是★5宗师的题目(球27到32颗),在开发用的 Mac 上,生成所花的时间平均也只有0.6秒左右。而且,每个难度都事先生成备用3道题,用掉后会在后台补充,所以玩的人几乎不用等待。
答案不一定只有一个
倒着生成的步骤,只是答案的其中一种。同一个棋盘,常常还有好几个别的答案。可以直接玩的页面里的“王球练习”棋盘,也是用同样的思路做的,16颗球的棋盘有超过300万种解法(解法有多少种?)。
应用的“提示”记得生成时的答案,所以只要在答案的路线上,就能马上告诉你下一步。偏离路线时,求解的程序会去找另一条路(用电脑求解)。
