回溯法.cpp

用回溯法求马周游问题,马在棋盘上走字步,从马开始的位置开始周游棋盘,遍历全棋盘后回到起点,是否可行,可行的就输出路径,路径并输入尝试过的路径数,跳过的路径数

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.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<<"     菜单:  1、实验说明    2、开始马周游问题的求解  3、退出  "<<endl;
		cout<<endl;	cout<<"      请输入您的选项(1  2  3   )    "<<endl;
		int cd;
		cout<<"    您的选项是:   ";
		cin>>cd;
		switch(cd)
		{
		case 1:{ 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 s[30][30];
    int i,j;
    int w=1;
    int num=0;
    int n;
    cout<<"   输入棋盘的大小: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>>x;
    cout<<"y=";
    cin>>y;
	 SYSTEMTIME st;
	GetLocalTime(&st);

 int b;
 b=st.wSecond*1000+st.wMilliseconds;
    x--;
    y--;
    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);
		GetLocalTime(&st);

 int a;
 a=st.wSecond*1000+st.wMilliseconds;
    
    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;
    if(m==n*n-1)
        cout<<"   存在一种合理过程"<<endl;
    cout<<"    一共尝试过：";
    cout<<num<<" 条路径"<<endl;
	cout<<"   共花时间为:  "<<a-b<<"毫秒  "<<endl;
	cout<<endl;
	cout<<endl;
	break;
			   }
	case 3:exit(1);break;
	default:cout<<"选择错误！  请重新选择！"<<endl;break;
		}

	}

}