跳马1.cpp

跳马算法的实现过程！跳马的源代码！请大家放心使用

// 跳马1.cpp : Defines the entry point for the console application.
//


//使用贪婪算法的跳马回路算法
//下面这个算法 可以求跳马问题的近似解，偶数100×100之内都可以计算。
//n*n的格子里，如果n为奇数，可用数学证明，它必然不存在一个跳马回路（用国际象棋的黑白棋盘可以得到启示）
 
 
//贪心法  
//跳马问题  
#include  <iostream.h>  
#include "stdafx.h"
#include  <iomanip.h>  
#include  <conio.h>  
#define  ROW   6      
#define  LINE  6       
#define  NUM  ROW*LINE         
int  board[ROW][LINE];
 //两个数组存储对应的偏移量  
int  stepRow[8] ={-1,-2,-2,-1,1,2,2,1};  
int  stepLine[8]={-2,-1,1,2,2,1,-1,-2};  
//求  (i,j)  的出口数，各个出口对应的号存在 a[]  中。
int  exitn(int i,int j,int s,int a[])
{  
           int  i1,j1,k,count;  
           for(count= k=0;k <8;k++)
		   {  
                i1=i+stepRow[(s + k)%8];  
                j1=j+stepLine[(s+ k)%8];  
                if(i1>=0&&i1<ROW&&j1>=0&&j1<LINE&&board[i1][j1]==0)
				{  
                     a[count++]=(s+k)% 8; 
				}  
           }  
           return  count;  
}  
//判断选择下个出口，s  是顺序选择法的开始序号  
int  next(int i ,int j,int s)
{  
           int m,kk,a[8],b[8],temp;  
           m = exitn(i,j,s,a);  
           if(m==0)    return  -1;      //没有出口的情况  
           for(int min=9,k=0;k<m;k++)
		   { //逐个考虑取下一步最少的出口的出口  
              temp=exitn(i+stepRow[a[k]],j+stepLine[a[k]],s,b);  
              if(temp<min)
			  {  
                  min=temp;  
                  kk =a[k];  
              }  
           }  
           return  kk;  
}  
 
 

int  main()  
{  
   int i,j,step,no,start;  
        //对每个位置的点都进行计算得到各个点的结果  
   for(int sx=0;sx<ROW;sx++)  
      for(int sy=0;sy<LINE;sy++)
	  {  
        start= 0;  
        do{  
           for(i=0;i<ROW;i++)  
              for(j=0;j<LINE;j++)  
                  board[i][j]= 0;  
           board[sx][sy]= 1;  
           i=sx;j=sy;  
           for(step=2;step<=NUM;step++)
           {  
              if((no=next(i,j,start))== -1)  
                break;  
              i+=stepRow[no];  
              j+=stepLine[no];  
              board[i][j]=step;  
           }  
           if(step>NUM||no==-1)  //if(step >NUM||no==-1)
                break;  
          }while(step<=NUM);  

		//printf("The step is:%d\n",step);//!!!!!
        if( ( no!=-1 && ((sx+2==i||sx-2==i)&&(sy+1==j||sy-1==j)) || ((sx+1==i||sx-1==i)&&(sy+2==j||sy-2==j)))   &&   step==(NUM+1) )// 
		{  
             cout<<"ok"<<endl;
			 //cout<<"The last step is:"<<step<<endl;
             for(i=0;i<ROW;i++)
			 {  
               for(j=0;j<LINE;j++)  
                  cout<<setw(5)<<board[i][j];  //打印 setw(5)为间隔 
               // cout<<board[i][j]<<'/t';
               cout<<endl; 
			 }
             return 0;
		}  
      }                   
   cout<<endl<<"no circle"<<endl;
   return  0;  
}