#include<iostream.h>
#include<conio.h>
int f( int,  int,const int [][8],const int [][8], int [],int []);
int p,q;
int main()
{
	int h=1,lowest1,lowest2;
	int accessibility[8][8]={{2,3,4,4,4,4,3,2},
	{3,4,6,6,6,6,4,3},
	{4,6,8,8,8,8,6,4},
	{4,6,8,8,8,8,6,4},
	{4,6,8,8,8,8,6,4},
	{4,6,8,8,8,8,6,4},
	{3,4,6,6,6,6,4,3},
	{2,3,4,4,4,4,3,2}};
	int array[8][8]={0};
	int horizontal[]={2,1,-1,-2,-2,-1,1,2};//the vertical and horizontal 
	//arrays help make the l shaped moves.
	int vertical[]={-1,-2,-2,-1,1,2,2,1};
	int currentrow,currentcolumn,x,y,movenumber;
	
	cout<<"Enter a row and a column for the horse's start position:"<<endl;
	cin>>currentrow>>currentcolumn;
	array[currentrow][currentcolumn]=h,
		accessibility[currentrow][currentcolumn] -=1;
	
	
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cout<<array[i][j]<<' ';
			if(j==7)
				cout<<endl<<endl;}
		
	}
	
	
	for (int z=0;z<63;z++)//this step is repeated 63 times .. for the 63 
		// moves in which the program has to choose the 
		//least accessible chesshouse
		
	{
		int lowest=9;
		for(int i=0;i<8;i++){
			movenumber=i;
			x=currentrow+vertical[movenumber]; 
			y= currentcolumn+horizontal[movenumber];
			
			if(x>-1 && x<8 && y>-1 && y<8)   //so the knight doesn't 
				//go out of the  chess 
				//board
			{
				
				if(array[x][y] == 0 && accessibility[x][y] <= lowest)
					//to make sure the knight  doesn't go to the same houses
					
				{                                                   
					
					
					
					if (accessibility[x][y] == lowest)
						//if the accessibility elements have the same value
					{
						{						
							lowest1=f(x,y,accessibility,array,horizontal, vertical);//call to the f function
							//to find the house that should 
							//the horse be moved to, has the least 
							//accessibility option in it's next move!
							lowest2=f(p,q, accessibility,array,horizontal, vertical);
							if (lowest1 < lowest2)
								lowest=accessibility[x][y],	p=x,q=y;
							
						}
						
					}
					
					else	lowest=accessibility[x][y], p=x,q=y;
				}	   
				
				
			}	
		}
		
		
		
		array[p][q]=h+1,h++,accessibility[p][q] -=1,
			currentrow=p,currentcolumn=q;
		
	}
	
	
	
	cout<<endl<<endl<<endl<<endl;
	for(i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cout<<array[i][j]<<' ';
			if(j==7)
				cout<<endl<<endl;}
		
	}
	
	cout<<endl<<endl<<endl<<endl;
	for(i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cout<<accessibility[i][j]<<' ';
			if(j==7)
				cout<<endl<<endl;}
		
	}
	
	return 0;
	}
	
	
	int f(int a,int b,const int accessibility[][8],const int array[][8],int horizontal[],int vertical[])
	{
		int x1,y1,lowest1=9,p1,q1,movenumber,lowest2,lowest3;
		{	
			
			for(int i=0;i<8;i++)
			{
				movenumber=i;
				x1=a+vertical[movenumber];
				y1=b+horizontal[movenumber];
				
				if(x1>-1 && x1<8 && y1>-1 && y1<8)
				{
					
					if(array[x1][y1] == 0 && accessibility[x1][y1] <= lowest1)
					{
						
						
						
						if (accessibility[x1][y1] == lowest1)
						{
							
							lowest2=f(x1,y1,accessibility,array,horizontal, vertical);
							lowest3=f(p1,q1,accessibility,array,horizontal, vertical);
							if (lowest2 < lowest3)
								lowest1=accessibility[x1][y1],	p1=x1,q1=y1;
							
						}
						
					}
					else	lowest1=accessibility[x1][y1], p1=x1,q1=y1;
				}	   
									
			}
		}
		return lowest1;//should i make a base case here or is this enough?
	}