一个硬币移动游戏的求解算法

这个游戏我是在光荣出的大航海时代4威力加强版(一个蛮古老的单机版PC游戏）上第一次见到的。与其说是个游戏，不如说是个智力题。这个题目是这样的：

有5个硬币，三个正面，两个反面，最初是间隔排列的，如图1所示。

图 1 五枚硬币的原始排列

每次移动只能移动相邻的2个不同的硬币，也就是移动的这两个硬币一定要一个是正面一个是反面，并且两个硬币是相邻的。可以向左或向右移动，但是移动的那个方向上必须有相邻的硬币。移动时还要跨过相邻的硬币。举个例子，比如第1、2两枚硬币可以向右移动，但是不可以向左移动，因为左边没有相邻的硬币。向右移动时要跨过右边所有相互挨着的硬币，如图2所示。

图 2 移动前两个硬币

如果移动方向上硬币是不连续的，则只能移动到第一个可以放硬币的地方，比如下面的例子，要将从左边数第3、第4两枚硬币向左边移动，则只能移动到中间的空位，不能跳过空位移到最左边，如图3所示。

图 3 另一个移动的例子

最终的目标是要移动成正的在一边，反的在另一边。

图 4 最终的目标

这个问题看似蛮简单的，但真正做起来就发现还是挺难的。我试了好久才找到答案。

但是这个题用计算机来解算却并不难，并且非常适于用递归算法来解算。下面是我编写的程序，因为这个程序的计算量不大，所以基本没有考虑计算效率问题，而是使程序尽量的简单、直白。

程序中用了个字符串来存放这些硬币的信息，’A’ 表示正面，’B’ 表示反面，空格表示空位。因此，字符串初始化为：" ABABA "。挪动硬币对应的就是改变字符串中AB的位置。相关的挪动硬币的操作放到了move 函数中。move 函数中传进一个整型参数 i，用来标识当前挪动的是哪两个硬币，向左挪动还是向右挪动。具体方法为，i的最低的一个bit 表示挪动方向，换句话说当i 为偶数时表示向左挪动，i为奇数时表示向右挪动硬币。i 的其余bit 表示当前挪动的是哪两个硬币。Move函数的返回值表示这次挪动是否成功了。

具体代码如下:

int main(){    string coins("        ABABA          ");    if(solve(coins, 5))    {        cout << coins << endl;    }    return 0;}

程序输出的结果如下：

AAABB
ABAA B
A ABAB
AABAB
ABAAB
ABABA

需要说明的是，因为是递归，所以输出的结果要从下往上看。