horse.cpp

这是一个洄溯法的源程序已经经过编译运行了没有错误

//黎国庄 [[e-mail]]
#include <stdio.h>
#include "SqStack.h"
#define n 8

int horizontal[]={2,1,-1,-2,-2,-1,1,2};
int vertical[]={-1,-2,-2,-1,1,2,2,1};
int board[n][n]={0};
int step=1;

SqStack s[n*n];
SqStack s1;//将各步的坐标记录



void exit(point p);//计算出下一步可能位置，按其各个位置下一个位置的和从小到大压栈到s[]中
int number(point p);//找出当前位置下一步的各种可能位置,计算可能之和
void next(point p);//找出各个位置并将其步数记录
bool legal(point p);//判断是否可行

void main()
{
	
	point p;
	printf("\n");
	printf("***************欢迎使用回溯法解决马周游问题****************\n\n");
	printf("***************下面请输入马的初始位置坐标 x(0-%d),y(0-%d):\n",n-1,n-1);
	printf("\n");
	scanf("%d%d",&p.x,&p.y);
	printf("\n");
	printf("周游路线如下:\n");
	printf("\n");
	while(!((p.x>=0)&&(p.x<n)&&(p.y<n)&&(p.y>=0)))
	{
		printf("输入不合法,请重新输入!\n");
		printf("\n");
		printf("请重新输入马的初始位置坐标 x(0-%d!),y(0-%d!):\n",n-1,n-1);
		printf("\n");
		scanf("%d%d",&p.x,&p.y);
		printf("\n");
		printf("周游路线如下:\n");
		printf("\n");
	} 

	
	next(p);
	
	for (int i=0;i<n;i++)//打印棋盘
	{
		for (int j=0;j<n;j++)
		{
			printf("%5d",board[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	printf("此次周游完毕!\n");
    main();
}



int   number(point p)//找出当前位置下一步的各种可能位置,计算可能之和
{
	              
	point p1;
	int j=0;

	
	for(int i=0;i<8;i++)
	{
		p1.x=p.x+horizontal[i];
		p1.y=p.y+vertical[i];
		if(legal(p1))
		{
			j++;
		}
	}
	return (j);
}


void next(point p)//找出各个位置并将其步数记录
{
		point p1,p2;
		InitStack(s[step]);
		InitStack(s1);//初始化栈
		board[p.x][p.y]=step;
		Push(s1,p);//压栈走过的点
		if(step<n*n)
		{
			exit(p);
			Pop(s[step],p2);
			if ((s[step].base==s[step].top&&number(p2)==0)&&step!=n*n-1)
			{
				Pop(s1,p1);
				board[p1.x][p1.y]=0;	

				--step;
				
				while (s[step].base==s[step].top)
				{
					Pop(s1,p1);
					board[p1.x][p1.y]=0;
					step--;

				}

 				Pop(s[step],p2);
				step++;
				next(p2);
			}//退栈，悔棋
		
			else if(number(p2)==0&&s[step].base!=s[step].top)
			{	
				Pop(s[step],p2);
				step++;
				next(p2);
			}
			else if (number(p2)!=0&&s[step].base==s[step].top)
			{
				
				step++;
				next(p2);
			}

			else 
			{
				step++;
				next(p2);
			}
		}
}



void exit(point p)//计算出下一步可能位置，按其各个位置下一个位置的和压栈到s[]中
{

	point temp;
 	point p1;
 	int j=0;
 	point ap[8]={0};
 	for(int i=0;i<8;i++)
 	{
 		p1.x=p.x+horizontal[i];
 		p1.y=p.y+vertical[i];
 		if(legal(p1))
 		{
			ap[j]=p1;
 			j++;
		}
	}//将下一步的可能位置储存在ap[]中
	
	
	for(int count=0;count<number(p)-1;count++)   //使用冒泡法，对下一步的八个规则的从大到小排序 
    {
		for(int k=0;k<number(p)-1;k++)
		{
			if (number(ap[k])<number(ap[k+1]))
			{
				temp=ap[k+1];
				ap[k+1]=ap[k];
				ap[k]=temp;
			}
		}
      }

	for (int t=0;t<number(p);t++)	
	{
		Push(s[step],ap[t]);
	}//将可能位置压栈到s[step]
}

bool legal(point p)//判断是否可行
{
	if((p.x>=0)&&(p.x<n)&&(p.y<n)&&(p.y>=0)&&(board[p.x][p.y]==0))
		return true;
	else
		return false;
}