C语言黑白子交换
问题描述
有三个白子和三个黑子如图1所示布置：| 白 | 白 | 白 | 黑 | 黑 | 黑 |
图1
游戏的目的是用最少的步数将图1中白子和黑子的位置进行交换，使得最终结果如图2所示：
| 黑 | 黑 | 黑 | 白 | 白 | 白 |
图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;
}
运行结果：No. 0:………………………..
| * | * | * | | @ | @ | @ |
………………………..
No. 1:………………………..
| * | * | | * | @ | @ | @ |
………………………..
No. 2:………………………..
| * | * | @ | * | | @ | @ |
………………………..
No. 3:………………………..
| * | * | @ | * | @ | | @ |
………………………..
No. 4:………………………..
| * | * | @ | | @ | * | @ |
………………………..
No. 5:………………………..
| * | | @ | * | @ | * | @ |
………………………..
No. 6:………………………..
| | * | @ | * | @ | * | @ |
………………………..
No. 7:………………………..
| @ | * | | * | @ | * | @ |
………………………..
No. 8:………………………..
| @ | * | @ | * | | * | @ |
………………………..
No. 9:………………………..
| @ | * | @ | * | @ | * | |
………………………..
No. 10:………………………..
| @ | * | @ | * | @ | | * |
………………………..
No. 11:………………………..
| @ | * | @ | | @ | * | * |
………………………..
No. 12:………………………..
| @ | | @ | * | @ | * | * |
………………………..
No. 13:………………………..
| @ | @ | | * | @ | * | * |
………………………..
No. 14:………………………..
| @ | @ | @ | * | | * | * |
………………………..
No. 15:………………………..
| @ | @ | @ | | * | * | * |
………………………..
