C语言黑白子交换

问题描述

有三个白子和三个黑子如图1所示布置：

游戏的目的是用最少的步数将图1中白子和黑子的位置进行交换，使得最终结果如图2所示：

游戏的规则是：

• (1) 一次只能移动一个棋子。
• (2) 棋子可以向空格中移动，也可以跳过一个对方的棋子进入空格。
• (3) 白色棋子只能往右移动，黑色棋子只能向左移动，不能跳过两个子。

请用计算机实现上述游戏。

问题分析

计算机解决这类问题的关键是要找出问题的规律，或者说是要制定一套计算机行动的规则。分析本题，先用人来解决问题，可总结出以下规则：

• (1) 黑子向左跳过白子落入空格，转（5）；
• (2) 白子向右跳过黑子落入空格，转（5）；
• (3) 黑子向左移动一格落入空格（但不应产生棋子阻塞现象），转（5）；
• (4) 白子向右移动一格落入空格（但不应产生棋子阻塞现象），转（5）；
• (5) 判断游戏是否结束，若没有结束，则转（1）继续。

所谓的“阻塞”现象指的是：在移动棋子的过程中，两个尚未到位的同色棋子连接在一起，使棋盘中的其他棋子无法继续移动。

产生阻塞的现象的原因是在第（2）步时，白棋子不能向右移动，只能将黑棋子向左移动。

总结产生阻塞的原因，当棋盘出现“黑、白、空、黑”或“白、空、黑、白”状态时,不能向左或向右移动中间的棋子，只移动两边的棋子。按照上述规则，可以保证在移动棋子的过程中，不会出现棋子无法移动的现象，且可以用最少的步数完成白子和黑子的位置交换。

算法设计

可以有4种移动方式（“〇”代表白子，“●”代表黑子，“△”代表空格，“〜”代表任意）：

• 白棋跳过黑棋：〜〇●△ 〜〜
• 黑棋跳过白棋：〜〜△●〇〜〜
• 白棋移向全格：〜〜〜○△〜〜
• 黑棋移向空格：〜〜〜●△〜〜

(1) 黑白棋要是能跳，则先跳。

根据游戏规则，如果出现下列情况1，黑棋不能往右，此时只能白棋跳过黑棋往右；同样，如果出现下列情况2，白棋不能往左，此时只能黑棋跳过白棋往左。

• 情况1:〜〇●△○〜〜
• 情况2:〜●△〇●〜〜

是否存在黑棋既能往左跳，存在白棋又可往右跳的可能性呢？即，情况3或情况4同 时存在的现象。

• 情况3:〜〇●△〇●〜
• 情况4:〇●△〇●〜〜

事实证明这两种情况是存在的。

(2) 棋子只能移动时。

①若向右移动白子不会产生阻塞，则白子向右移动，分i=1和i>1两种情况：

i=1时，白棋只能往右移，即：

• ○△〜〜〜〜〜

i>1时，i处的白棋只有在i-1和i+2位置上的棋子不同时才能往右移动，即情况5或情况6。

• 情况5:〜●○△○〜〜
• 情况6:〜○○△●〜〜

分析：如果i-1和i+2位置上的棋子相同时，即情况7。

• 情况7:〜〜●○△●〜

如果将白子向左移动到空格处，会转变成情况8。如果在情况7时，第二个任意子位置是白子，白子跳过黑子右移，会出现两个白子相连的情况，如情况9，将产生阻塞；或者出现倒数第二个黑子跳过白子左移，出项两个黑子相连的情况，如情况10，同样产生阻塞。

• 情况8: 〜〜●△○●〜
• 情况9:〜△●〇〇●〜
• 情况10:〜〜●●○△〜

相应代码如下：

for(i=0; flag&&i<6; i++)
    if(t[i]==1 && t[i+1]==0 && (i==0 || t[i-1]!=t[i+2]))

②若向左移动黑子不会产生阻塞，则黑子向左移动，分i=5和i>1两种情况:

i=5，黑棋只能往左移：

• 〜〜〜〜〜△●

i>1时，i+1处的黑棋只有在i-1和i+2位置上的棋子不同时才能往左移动，即，情况11或情况12。

• 情况11:〜○△●●〜〜
• 情况12:〜●△●○〜〜

相应代码如下：

for(i=0; flag&&i<6; i++)
if(t[i]==0 && t[i+1]==2 && (i==5||t[i-1]=t[i+2]))

下面是完整的代码：

#include<stdio.h>
int number;
void print(int a[]);
void change(int *n, int *m);
int main()
{
    int t[7]={1,1,1,0,2,2,2};  /*初始化数组1：白子 2：黑子 0：空格*/
    int i, flag;
    print(t);
    /*若还没有完成棋子的交换则继续进行循环*/
    while(t[0]+t[1]+t[2]!=6 || t[4]+t[5]+t[6]!=3)  /*判断游戏是否结束*/
    {
        flag=1;  /*flag为棋子移动一步的标记，flag=1表示尚未移动棋子，
                  flag=0表示已经移动棋子*/
        for(i=0; flag&&i<5; i++)  /*若白子可以向右跳过黑子，则白子向右跳*/
            if(t[i]==1 && t[i+1]==2 && t[i+2]==0)
            {
                change(&t[i], &t[i+2]);
                print(t);
                flag=0;}
        for(i=0; flag&&i<5; i++)  /*若黑子可以向左跳过白子，则黑子向左跳*/
            if(t[i]==0 && t[i+1]==1 && t[i+2]==2)
            {
                change(&t[i], &t[i+2]);
                print(t);
                flag=0;
            }
        for(i=0; flag&&i<6; i++)  /*若向右移动白子不会产生阻塞,则白子向右移动*/
            if(t[i]==1 && t[i+1]==0 && (i==0||t[i-1]!=t[i+2]))
            {
                change(&t[i], &t[i+1]);
                print(t);
                flag=0;
            }
        for(i=0; flag&&i<6; i++)  /*若向左移动黑子不会产生阻塞，则黑子向左移动*/
            if(t[i]==0 && t[i+1]==2 && (i==5||t[i-1]!=t[i+2]))
            {
                change(&t[i], &t[i+1]);
                print(t);
                flag=0;
            }
    }
    return 0;
}
void print(int a[])
{
    int i;
    printf("No. %2d:………………………..\n", number++);
    printf(" ");
    for(i=0; i<=6; i++)
        printf(" | %c",a[i]==1?'*':(a[i]==2?'@':' '));
    printf(" |\n ………………………..\n\n");
}
void change(int *n, int *m)
{
    int term;
    term=*n;
    *n=*m;
    *m=term;
}

运行结果：