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


		这个游戏我是在光荣出的大航海时代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函数的返回值表示这次挪动是否成功了。
具体代码如下:
[cpp]  
static bool move(string &coins, int i)  
{  
    int dir = i % 2; // 0 表示左移，1 表示右移  
    i = i / 2;  
    if(coins[i] == ' ' || coins[i + 1] == ' ' || coins[i] == coins[i + 1])  
    {  
        return false; //无法移动当前硬币  
    }  
    if( dir == 0 ) //向左移  
    {  
        if( coins[ i - 1] == ' ') //左边无硬币，不能移动  
        {  
            return false;  
        }  
        else  
        {  
            string::size_type j = i - 2;  
            while( coins[j] != ' ' && j > 1) {j --;}  
            coins[j - 1] = coins[i];  
            coins[j] = coins[i + 1];  
            coins[i] = ' ';  
            coins[i + 1] = ' ';  
        }  
    }  
    else  
    {  
        if( coins[i + 2] == ' ') //右边无硬币，不能移动  
        {  
            return false;  
        }  
        else  
        {  
            string::size_type j = i + 3;  
            while(coins[j] != ' ' && j < coins.size() - 1) {j ++;}  
            coins[j] = coins[i];  
            coins[j + 1] = coins[i + 1];  
            coins[i] = ' ';  
            coins[i + 1] = ' ';  
        }  
    }  
    return true;  
}  
 
isSeperated 函数判断是否将硬币分开了，算法很简单，肯定有更高效的算法，我没有在这上面多花心思，因为对于这个小程序来说，肯定是写程序所花的时间远大于程序运行所话的时间。因此我追求的是如何能快速的写完这个程序，而不是如何让这个程序跑的更快。下面是代码：
[cpp]  
static bool isSeperated(string coins)  
{  
    int first = 0, last = coins.size() - 1;  
    while(coins[first] == ' ') {first ++;} //找到这些硬币的开始位置  
    while(coins[last] == ' ') {last --;} //找到这些硬币的结束位置  
    if(coins[first] == coins[last] ) return false;// 头尾的两个硬币相同，肯定没有排列好  
    int i = first + 1, j = last - 1;  
    while(coins[i] == coins[first] || coins[i] == ' '){i ++;} //找到第一个与头硬币不同的硬币  
    while(coins[j] == coins[last] || coins[j] == ' '){j --;}  //找到最后一个与尾硬币不同的硬币  
    if( i != j + 1) return false;  
    return true; // 到这里说明已经排列好了  
}  
 
Solve 函数负责解算，算法很简单，简单的说就是穷举法，把可能的移动方法都试一下，必然就能得到正确的步骤了。唯一需要说明的是对于这个问题，可以移动的步数是无穷的。所以要限定搜索深度，也就是要限定最多移动多少步，这样穷举才能有个尽头。按层数（步数）搜索自然是递归算法写起来最方便。下面是代码：
[cpp]  
bool solve(string coins, int depth)  
{  
    string coins2 = coins;  
    int first = 0;  
    int last = coins.size() - 1;  
    while(coins[first] == ' ') {first ++;}  
    while(coins[last] == ' ') {last --;}  
  
    for( int i = 2 * first; i < 2 * (last - 1); i++ )  
    {  
        if( move(coins, i) )  
        {// 表明可以这样移动  
            depth --; // 记录移动了几步  
            if( isSeperated(coins) )  
            {  
                // 完成了，输出结果  
                cout << coins << endl;  
                return true;  
            }  
            else if( depth != 0 && solve(coins, depth) )// 在当前移动的基础上继续移动  
            {  
                cout << coins << endl;  
补充：软件开发 , C++ ,