Subj : Knight's tour
To   : comp.programming
From : forayer
Date : Wed Jun 29 2005 11:51 am

Hi there,
	Is there any particular pattern in which to short-list the
possible squares in the Knight's Tour problem such that it is solved 
with few back-tracking?
I did this implementation where I check row-wise
| |1| |2| |
|3| | | |4|
| | |N| | |
|5| | | |6|
| |7| |8| |
But in this case, if I start from top-left corner, it takes 17739767
calls to the visit func before a solution is found! And if I start from
the lower-right corner, it seems to take forever to find a solution.

Regards,
forayer

Here's the code I use to visit the 'next' square:
/*	| |1| |2| |	*/
	if(x>1) {
		t = x-2;
		if(y>0) {
			u = y-1;
			if( board[t][u]==0 )
				if( visit(t,u,v+1) )
					return 1;
		}
		if(y<7) {
			u = y+1;
			if( board[t][u]==0 )
				if( visit(t,u,v+1) )
					return 1;
		}
	}
/*	|3| | | |4|	*/
	if(x>0) {
		t = x-1;
		if(y>1) {
			u = y-2;
			if( board[t][u]==0 )
				if( visit(t,u,v+1) )
					return 1;
		}
		if(y<6) {
			u = y+2;
			if( board[t][u]==0 )
				if( visit(t,u,v+1) )
					return 1;
		}
	}
/*	|5| | | |6|	*/
	if(x<7) {
		t = x+1;
		if(y>1) {
			u = y-2;
			if( board[t][u]==0 )
				if( visit(t,u,v+1) )
					return 1;
		}
		if(y<6) {
			u = y+2;
			if( board[t][u]==0 )
				if( visit(t,u,v+1) )
					return 1;
		}
	}
/*	| |7| |8| |	*/
	if(x<6) {
		t = x+2;
		if(y>0) {
			u = y-1;
			if( board[t][u]==0 )
				if( visit(t,u,v+1) )
					return 1;
		}
		if(y<7) {
			u = y+1;
			if( board[t][u]==0 )
				if( visit(t,u,v+1) )
					return 1;
		}
	}

.