递归：以俄罗斯跳棋为例
先介绍一下俄罗斯跳棋，其界面如下：
走法：盘面开局32个棋子，中间为空；走子时隔一子对称跳，被隔棋子被吃掉。谁能走成最后剩下一子的局面，即为赢。
我是从一个朋友得知俄罗斯跳棋的。总是赢不了，最后只能靠计算机帮忙了。可以自我安慰的是，周围的人还没有一个只靠自己就能赢的。不算丢脸，呵呵。
很明显这个问题类似八皇后问题，用递归解比较简洁。解答程序主要部分为Russia()函数，Next()是用作寻找下一步的函数。解答程序如下：
//俄罗斯跳棋
#include <stdio.h>
#include <stdlib.h>
int ChessBoard[7][7]={-10,-10,1,1,1,-10,-10,
-10,-10,1,1,1,-10,-10,
1,1,1,1,1,1,1,
1,1,1,0,1,1,1,
1,1,1,1,1,1,1,
-10,-10,1,1,1,-10,-10,
-10,-10,1,1,1,-10,-10}; //为1处即棋盘
int step[4][31];//记录每一步：x y delta(x) delta(y)
int delta[2]; // 临时数组 记录delta(x) delta(y) 共有四个方向
int Next(int x,int y); //下一步
int Russia(int x,int y,int Count)// 主循环
{
int i,j;
int Result=0;
if(Count==31)
return 1;
else if(Next(x,y)==1)
{
step[0][Count]=x;
step[1][Count]=y;
step[2][Count]=delta[0];
step[3][Count]=delta[1];
ChessBoard[x][y]=0;
ChessBoard[x+delta[0]/2][y+delta[1]/2]=0;
ChessBoard[x+delta[0]][y+delta[1]]=1;
for(i=0;i<7;i++)
for(j=0;j<7;j++)
{
if(ChessBoard[i][j]==1) Result+=Russia(i,j,Count+1);
if(Result>0) break;
}
if(Result>0)
{
printf(" %d ",Count);
return 1;
}
else
{
if((x!=step[0][Count])&&y!=step[1][Count]) exit(1);
ChessBoard[x][y]=1;
ChessBoard[x+step[2][Count]/2][y+step[3][Count]/2]=1;
ChessBoard[x+step[2][Count]][y+step[3][Count]]=0;
step[0][Count]=0;
step[1][Count]=0;
step[2][Count]=0;
step[3][Count]=0;
return 0;
}
}
else
return 0;
}
int Next(int x,int y)//下一步
{
if(((x+2)<7)&&ChessBoard[x+2][y]==0&&ChessBoard[x+1][y]==1){
delta[0]=2;
delta[1]=0;
return 1;
}
if(((y-2)>0)&&ChessBoard[x][y-2]==0&&ChessBoard[x][y-1]==1){
delta[0]=0;
delta[1]=-2;
return 1;
}
if(((x-2)>0)&&ChessBoard[x-2][y]==0&&ChessBoard[x-1][y]==1){
delta[0]=-2;
delta[1]=0;
return 1;
}
if(((y+2)<7)&&ChessBoard[x][y+2]==0&&ChessBoard[x][y+1]==1){
delta[0]=0;
delta[1]=2;
return 1;
}
return 0;
}
void main()
{
int i,j;
for(j=0;j<31;j++)
for(i=0;i<4;i++)
step[i][j]=0;
Russia(3,5,0);
for(j=0;j<31;j++){
for(i=0;i<4;i++){
printf(" %d, ",step[i][j]);
}
printf(" \n");
}
}
需要程序及源代码，可以在如下网址下载：
http://turbulence.myshow.cn之“网络硬盘”－“/我的作品/历史上最难的小游戏/”
希望能对大家理解递归有所帮助。
