/* Knight's Tour Problem - a kind of undirected Hamiltonian circuits
   Using an advanced algorithm - at least 10000 times faster than simple backtracking
   The key idea is to detect bi-degree nodes and also the art of programming
   Enjoy it!

   Author : Fei Lu
   Email  : flylandcs@hotmail.com
*/


#define true 7361
#define false 28456
#define N 8
#define INTERVAL 1	// Display the result on every 100 solutions 
#define Magic_SUM 260

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
#include <assert.h>

// Optimized for 8x8 board
#define ROW(x) (x>>3)
#define COL(x) (x&7)
//#define ROW(x) (x/N)
//#define COL(x) (x%N)

double duration;
unsigned int nSolution=0;

//	delta-i, delta-j for 8 neighbourhood
int iDir[8]={-2,-1,	1,	2,	2,	1,	-1,	-2};
int jDir[8]={1,	2,	2,	1,	-1,	-2,	-2,	-1};

/*	At each position (i,j), the knight has t directions to go
	Define: nBranch[here]=t, (t<=8) ;		"here" is encoded as i*N+j,  (i,j: 0 ... N-1)

	Given the current position: here and 
	the k(th) direction, which the knight chooses to move, 
	Define: branch[here][k] = the next position 

	The problem is now abstracted as a graph problem. 
	There are N^2 nodes and their connections are stored in the array called "branch"
*/
int branch[N*N][8],	nBranch[N*N];

//	~~~~~~ states involved in path searching ~~~~~~
int board[N*N];	// board[v] = t, indicating node "v" is visited at the t(th) step, (t: 1 ... N*N), 
				// board[v] = 0 means this node has not been visited yet.
int degree[N*N];// degree[v] is the number of non-visited neighbours of node v
				// ****** ASSERTION ********
				// A. If a non-visited node has a degree of two, then one is for in-degree, one is for out-degree.
				// B. If the knight is to arrive on node v: 
				//		1. If a neighbour has a degree of 1, it must be the endpoint
				//		2. If the "endpoint" is already defined, 
				//					there can exist ONLY one neighbour whose degree is 2. 
				//					This neighbour must be visited immediatelly after node v.
				//		3. If the "endpoint" is not defined,
				//					there can exist AT MOST two neighbours whose degree is 2.
				//					One of this neighbour must be defined as endpoint
				//					The other must be visited immediatelly after node v.
				//
				// "neighbours" mentioned in the above assertions refers to 
				//		non-visited neighbours
 
int nBranch_to_go[N*N];		// nBranch_to_go[here]: the number of non-visited neighbours
int branch_to_go[N*N][8];	// branch_to_go[here]: array to store all non-visited neighbours
int endpoint_set[N*N][8];	// endpoint_set[here][d]=true, if visiting branch_to_go[here][d] 
							//		will cause an endpoint to appear somewhere else

int path[N*N+1];// path[k] = v, where v is the k(th) visited node. Note: v can be decoded into (i,j), v=i*N+j
int dir[N*N+1];	// dir[k] = t, where the knight at k(th) step is searching the t(th) edge  
int n;			// the current step. n: 1 ... N*N
int endpoint_Defined;	// If there exist one non-visited node whose degree is one, then it is defined as the endpoint

int rsum[N],csum[N];	// sum of each row/column
int cn[N],rn[N];		// number of empty holes left in each row/coloum
int up[N+1];			// up[i]      = N*N + ... + N*N-i+1	 
int down[N*N+2][N+1];	// down[n][i] = n + ... + (n-i+1)

//	Syntactic sugars. Do not use the following arrays in time-critical functions.
int (*board2D)[N]=(int(*)[N])&board;	// board2D[N][N]
int (*degree2D)[N]=(int(*)[N])&degree;	// degree2D[N][N]


void printBoard()
{
	int i,j;
	char buf[80];
	for(i=0; i<4*N+1; i++) buf[i]='-';
	buf[i]=0; 
	printf("%s\n",buf);
	for(i=0; i<N; i++){
		for(j=0; j<N; j++){
			if(0==board2D[i][j]) printf("|   ");
			else printf("|%3d",abs(board2D[i][j]));
		};
		printf("|\n");
	};
	printf("%s\n",buf);
	//getch();
}

//	Will be invoked when each solution is found
void record()
{
	nSolution++;
	if(nSolution%INTERVAL==0){
		printf( "Solved %u  %8.2f seconds\n", nSolution, duration);
		printBoard();
	};
}




// Roll back the global states ( degree[] ) changed during degree checking 

inline void rollback_degree(int v,int count)
{
int i;
	for(i=0;i<count;i++) degree[branch_to_go[v][i]]++;	
}




// Roll back the global states ( rsum[],csum[],rn[],cn[] ) changed during magic checking 
inline void rollback_magic(int here, int n)
{
	int r=ROW(here);
	int c=COL(here);
	rsum[r] -= n; 
	csum[c] -= n;
	rn[r]++; cn[c]++;
}







/*	Function: check_and_calc_degree(int v)
	Precondition: 
		Node v is tentatively being visited. (globle status: board[v]=n+1 )
	
	Purpose: 
		Cut unnecessary search branches to boost performance.
		This is based on several assertions on degrees of non-visited nodes.

	Postcondition:
		If degree assertions fail, return false.
		Else return true and
			 branch_to_go is filled with an array of to-be-visited neighbours. 
		
		If return false, no side effects.
		If return true, side-effects: it changes degree, branch_to_go, nBranch_to_go
*/
inline int check_and_calc_degree(int v)
{	
	int u;				// u is a neighbour of v
	int m;				// the number of edges of node v. e.g. m==8 for 8 directions
	int d;				// the d(th) edge/direction  
	int degree2=0;		// count the number of nodes whose degree is 2.
	int u2[2];			// remember those neighbours whose degree is 2
	int u2index;		// remember the index of the first neighbour whose degree is 2
	int count=0;
	int atmost;
    int i;
////////// check if visiting node v will lead to a dead end /////////

	if(endpoint_Defined) atmost=1;	// At most 1 degree-of-2 node can exist
	else atmost=2;					// At most 2 degree-of-2 nodes can exist	
	
    m=nBranch[v];
	for(d=0; d<m; d++){
		u=branch[v][d];
		if(board[u]>0) continue;

		if(degree[u]==2){
			if(degree2>=atmost){
				rollback_degree(v,count);				//Check failed
				return false;
			};
			u2[degree2++]=u;	
			u2index=count;
		};

		degree[u]--;	// If v is visited, neighbours' degree must be decreased
		branch_to_go[v][count++]=u;	
	};
/////////////////////////////////////////////////////////
	nBranch_to_go[v]=count;
	memset(endpoint_set[v],0,sizeof(int)*8);

	if(degree2==2){					// Case 1: TWO degree-of-two nodes and endpoint_Defined
		// assert: endpoint_Defined==true
		nBranch_to_go[v]=2;
		branch_to_go[v][0]=u2[0];
		branch_to_go[v][1]=u2[1];
		endpoint_set[v][0]=true;
		endpoint_set[v][1]=true;

	}else if(degree2==1){
		if(endpoint_Defined){		// Case 2: only ONE degree-of-two node and endpoint_Defined
			nBranch_to_go[v]=1;
			branch_to_go[v][0]=u2[0];
		}else{						// Case 3: only ONE degree-of-two and NO endpoint_Defined
			for(i=0; i<count; i++){
				if(i!=u2index) endpoint_set[v][i] = true;
			}
		}
	}
	return true;
}

// When the knight retreats from node v, neighbours' degrees should be restored
inline void restore_degree(int v)
{
	int d,m,u;
	m=nBranch[v];
	for(d=0; d<m; d++){
		u=branch[v][d];
		if(board[u]>0) continue;
		degree[u]++;	// restore the degree if u is not visited
	};
}


// Precondition:  label (n+1) is going to be placed at node "there"
// Postcondition: No side-effect if check fails
//                rsum,csum,rn,cn are changed if check succeeds
inline int magic_check(int there)
{
	int s1,s2;
	int r,c;
	r=ROW(there);
	c=COL(there);

	s1=rsum[r] + (n+1);
	if( s1 + up[rn[r]-1] < Magic_SUM )  return false;
	if( s1 + down[n+2][rn[r]-1] > Magic_SUM )  return false;

	s2=csum[c] + (n+1);
	if( s2 + up[cn[c]-1] < Magic_SUM )  return false;
	if( s2 + down[n+2][cn[c]-1] > Magic_SUM )  return false;

	rsum[r] = s1;
	csum[c] = s2;
	rn[r]--;
	cn[c]--;
	return true;
}

inline void retreat(int here)
{
	rollback_magic(here,n);

	restore_degree(here);
	board[here]=0;
	
	int v = path[n-1];
	int d = dir[n-1];

	if(endpoint_set[v][d]==true){
		endpoint_Defined=false;
	};
	n--;
}

/* Depth-First-Search */
void Travel()
{
	int m,d;
	int here,there;
	int rollback_endpoint_Defined;	// Used for rollback

	while(n>=1){
LOOP:
		/*if(board2D[0][0]==1 &&
		   board2D[1][2]==2 &&
		   board2D[2][0]==3)/* &&
		   board2D[4][1]==4)/* &&
		   board2D[3][3]==5/* &&
		   board2D[5][4]==6 &&
		   board2D[3][5]==7 )/*&&
			board2D[0][1]==10)/* && 
			board2D[0][2]==35)/* &&
			board2D[0][3]==28 &&
			board2D[0][4]==25)/* &&
			board2D[0][5]==12)*/
		//if(board2D[0][4]==25)
		//if(board2D[4][3]==18)
		//if(board2D[4][4]==23)
		/*if(board2D[4][0]==21 && board2D[3][0]==30)
		{
			printBoard(); 
			//printDegree();
			for(int i=0; i<6; i++) printf("%d ",rsum[i]);
			printf("********\n");
			//getch();
		};
		printBoard(); 
			for(int i=0; i<6; i++) printf("%d ",rsum[i]);
			printf("********\n");
		getch();

/*		if(n==7){
			printBoard(); 
			for(int i=0; i<6; i++) printf("%d ",rsum[i]);
			printf("********\n");
		}

		if(n==23){
			printBoard(); 
			for(int i=0; i<6; i++) printf("%d ",rsum[i]);
			printf("********\n");
		}
*/
//		if(n<34) return;
		here=path[n];
		m=nBranch_to_go[here];

		for(d=++dir[n]; d<m; d++){
			there=branch_to_go[here][d]; 
			
			// tentatively going to the n+1(th) grid. Going to check magic assertions and degree assertions
			if( magic_check(there)==false ) continue;

			board[there]=n+1;

			if(!endpoint_Defined && endpoint_set[here][d]){
				rollback_endpoint_Defined=false;
				endpoint_Defined=true;
			};

			if( check_and_calc_degree(there)==false){
				endpoint_Defined=rollback_endpoint_Defined;
				board[there]=0; 
				rollback_magic(there,n+1);	// magic_check has some side-effects, need a rollback
				continue;
			}

			// Check passed,  proceed to the n+1(th) grid 
			dir[n++]=d;
			path[n]=there;
			dir[n]=-1;

			if(n<N*N) goto LOOP;
			else{	
				// now we have visited N*N nodes, thus the solution is found
				record();	
				retreat(there);
				break;	// and retreat
			}
		}
		retreat(here); 
	}
}

inline void init()
{
	int i,j,n,sum;

	
	for(i=0; i<=N; i++){
		sum=0;
		for(j=N*N; j>N*N-i; j--) sum+=j;
		up[i]=sum;
	}

	for(n=1; n<=N*N+1; n++){
		for(i=0; i<=N; i++){
			sum=0;
			for(j=0; j<i; j++) sum+=n+j;
			down[n][i]=sum;
		}
	}
}

void init_each()
{
	int i,j,ip,jp,k;
	int count;

	memset(board,0,sizeof(board));
	memset(dir,-1,sizeof(dir));
	memset(endpoint_set,0,sizeof(endpoint_set));  // set to be false

	memset(rsum,0,sizeof(rsum));
	memset(csum,0,sizeof(rsum));
	for(i=0; i<N; i++){
        rn[i]=N;
		cn[i]=N;
	}

	// Calculate the degree of each node
	for(i=0; i<N; i++){
		for(j=0; j<N; j++){
			count=0;
			for(k=0; k<8; k++){
				ip=i+iDir[k];
				jp=j+jDir[k];
				if(ip<0 || jp<0 || ip>=N || jp>=N) continue;
				branch[i*N+j][count]=ip*N+jp;
				count++;
			};
			degree[i*N+j]=nBranch[i*N+j]=count;
		};
	};
	endpoint_Defined = false;
	n=0;
}

/* Force the knight to go to the next position(r,c), can be used in testing */
void go(int r,int c)
{
	int there=r*N+c;
    int i,a1,a2;
	path[n+1]=there;
	board[there]=n+1;
	if(n>=1){
		int v = path[n];
		int m = nBranch_to_go[v];
		for(i=0; i<m; i++){
			dir[n]++;
			if(branch_to_go[v][i]==there) break;
		}
		assert(i<m);
		if(endpoint_set[v][i]) endpoint_Defined=true;
	};
	a1=check_and_calc_degree(path[n+1]);
	assert( a1 );
	a2=magic_check(path[n+1]);
	assert( a2 );
	n++;
}




void search_all()
{
	int i,j;
	for(i=0; i<N; i++){
		for(j=0; j<N; j++){
			init_each();
			go(i,j);
			Travel();	
		}
	}
}
void search_1()
{
	init_each();
	go(0,0); // 1
	go(1,2); // 2
	go(3,1); // 3
	go(2,3); // 4
	go(0,4); // 5
	go(1,6); // 6
	go(3,7); // 7
	go(2,5); // 8
	go(4,4); // 9
	go(5,6); // 10
	go(7,7); // 11
	go(6,5); // 12
	go(7,3); // 13
	go(6,1); // 14
	go(4,2); // 15
	go(5,0); // 16
	go(6,2); // 17
	go(7,0); // 18
	go(5,1); // 19
	go(4,3); // 20

	Travel();
}

int main()
{
	init();

	//search_all();
	search_1();

	duration = 0;
	printf("Summary:\n");
	printf("Solved %u  %8.2f seconds\n", nSolution, duration);
return 0;
}