這個游戲我是在光榮出的大航海時代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;
return true;
}
else
{
// 到這裡說明當前的移動是不對的
coins = coins2;
depth ++;
continue; // 試探下一種移動
}
}
}
// 到這裡說明所有的移動方式都試過了，全都不行
return false;
}
最後是主程序，就幾行，不用多解釋：
[cpp]
int main()
{
string coins(" ABABA ");
if(solve(coins, 5))
{
cout << coins << endl;
}
return 0;
}
程序輸出的結果如下：
AAABB
ABAA B
A ABAB
AABAB
ABAAB
ABABA
需要說明的是，因為是遞歸，所以輸出的結果要從下往上看。
