回溯法.cpp

用回溯法实现马周游

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <Windows.h>
using namespace std;
inline int good(int x,int y,int s[30][30],int n)
{
    if(x>=0&&x<=n-1&&y>=0&&y<=n-1&&s[y][x]==88)
        return 1;
    else
        return 0;
}

void main()
{
		cout<<" * * * * * * * * 欢迎进入本实验 * * * * * * * "<<endl;
	int flag=1;
	while(flag=1)
	{
      cout<<endl;
		cout<<"菜单:"<<endl<<"1、实验说明"<<endl<<"2、开始马周游问题的求解"<<endl<<"3、退出"<<endl;
		cout<<endl;	cout<<" 请输入您的选项(1  2  3)    "<<endl;
		int cd;
		cout<<" 您的选项是:   ";
		cin>>cd;
		switch(cd)
		{
		case 1:{
			cout<<"程序功能：实现马周游棋盘，最后回到起点"<<endl<<"实现方法：回溯法"<<endl;
			cout<<"作者：骆宏峰"<<endl;
			break;}
		case 2:{
    enum road{d11,d12,d21,d22,d31,d32,d41,d42};
    road d[100];
    int m=0;
    int x=0,y=0;
	int p=0,q=0;
    int s[30][30];
    int i,j;
    int w=1;
    int num=0;
    int n;
    cout<<"   输入棋盘的大小(不大于10):n=";
    cin>>n;
    for(i=0;i<n;++i)
        for(j=0;j<n;j++)
            s[i][j]=88;
    cout<<"  原始棋盘的情况"<<endl;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            cout<<s[i][j]<<" ";
        cout<<endl;
    }
    cout<<"   输入马在棋盘中的位置:"<<endl;
    cout<<"x=";
    cin>>p;
    cout<<"y=";
    cin>>q;

    p--;
    q--;
	x=p;
	y=q;
    d[0]=d11;
    s[y][x]=1;
    do{
             if(d[m]==d11&&good(x+1,y-2,s,n)){x++;y=y-2;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d12&&good(x+2,y-1,s,n)){x=x+2;y--;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d21&&good(x+2,y+1,s,n)){x=x+2;y++;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d22&&good(x+1,y+2,s,n)){x++;y=y+2;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d31&&good(x-1,y+2,s,n)){x--;y=y+2;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d32&&good(x-2,y+1,s,n)){x=x-2;y++;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d41&&good(x-2,y-1,s,n)){x=x-2;y--;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d42&&good(x-1,y-2,s,n)){x--;y=y-2;d[++m]=d11;s[y][x]=++w;num++;}
        else{
            while(d[m]==d42){
                m--;
                if(d[m]==d11){s[y][x]=88;--w;x--;y=y+2;}
                if(d[m]==d12){s[y][x]=88;--w;x=x-2;y++;}
                if(d[m]==d21){s[y][x]=88;--w;x=x-2;y--;}
                if(d[m]==d22){s[y][x]=88;--w;x--;y=y-2;}
                if(d[m]==d31){s[y][x]=88;--w;x++;y=y-2;}
                if(d[m]==d32){s[y][x]=88;--w;x=x+2;y--;}
                if(d[m]==d41){s[y][x]=88;--w;x=x+2;y++;}
                if(m!=0&&d[m]==d42){s[y][x]=88;--w;x++;y=y+2;}
            }
            d[m]=road(d[m]+1);
        }
    }while((m!=0||d[0]!=d42||good(x-1,y-2,s,n))&&m!=n*n-1||(p-x)*(p-x)+(q-y)*(q-y)!=5);
    
    cout<<"      马跳之后的情况(数字表示跳跃先后顺序)"<<endl;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            cout<<setfill('0')<<setw(2)<<s[i][j]<<" ";
        cout<<endl;
    }
    cout<<"    跳过的路径一共有"<<m<<"条"<<endl;
    if(m==0)
        cout<<"  不存在合理过程"<<endl;

    cout<<"    一共尝试过：";
    cout<<num<<" 条路径"<<endl;

	cout<<endl;
	cout<<endl;
	break;
			   }
	case 3:exit(1);break;
	default:cout<<"选择错误！  请重新选择！"<<endl;break;
		}
	}
}