= Knight Tour =

<<TableOfContents>>

== Problem Description ==

Find a tour for the knight piece that starts at any square, travels all squares, and comes back to the origin, following the rules of chess.

== Predicates ==

 * '''Input''': {{{size/1, givenmove/4}}}

 * '''Output''': {{{move/4}}}

== Input format ==
The input file contains one atom {{{size(N)}}}, which states that the chess board size is N*N and a number of atoms {{{givenmove(X1,Y1,X2,Y2)}}}. The rows of the board are numbered 1, 2, and so on up to N from top to bottom, and the columns are numbered 1, 2, and so on up to N from left to right.  In this way, each square can be represented by a unique pair of coordinates.

== Output format ==

The output is a tour defined as a predicate 

{{{move(X1,Y1,X2,Y2). move(X2,Y2,X3,Y3). ... move(Xn,Yn,X1,Y1).}}}

where each atom represents a valid move of the knight, all the squares are connected, and the last move brings the knight back to the origin. Moreover, the path contains all moves specifices by the givenmove predicate.  

== Example(s) ==

Input:
{{{
size(8). givenmove(7,5,8,7). givenmove(1,7,3,6).
}}}
Output:
{{{
move(1,1,2,3). move(2,3,4,2). move(4,2,2,1). move(2,1,1,3). move(1,3,2,5). move(2,5,3,7). move(3,7,1,8). move(1,8,2,6). move(2,6,1,4). move(1,4,2,2). move(2,2,3,4). move(3,4,1,5). move(1,5,2,7). move(2,7,4,6). 
move(4,6,5,8). move(5,8,6,6). move(6,6,5,4). move(5,4,7,5). move(7,5,8,7). move(8,7,6,8). move(6,8,4,7). move(4,7,2,8). move(2,8,1,6). move(1,6,3,5). move(3,5,4,3). move(4,3,5,5). move(5,5,7,4). move(7,4,8,2). 
move(8,2,6,1). move(6,1,7,3). move(7,3,8,1). move(8,1,6,2). move(6,2,4,1). move(4,1,3,3). move(3,3,4,5). move(4,5,5,3). move(5,3,7,2). move(7,2,5,1). move(5,1,6,3). move(6,3,7,1). move(7,1,8,3). move(8,3,6,4). 
move(6,4,8,5). move(8,5,7,7). move(7,7,6,5). move(6,5,8,4). move(8,4,7,6). move(7,6,8,8). move(8,8,6,7). move(6,7,8,6). move(8,6,7,8). move(7,8,5,7). move(5,7,3,8). move(3,8,1,7). move(1,7,3,6). move(3,6,4,8). 
move(4,8,5,6). move(5,6,4,4). move(4,4,5,2). move(5,2,3,1). move(3,1,1,2). move(1,2,2,4). move(2,4,3,2). move(3,2,1,1). 
}}}
== Notes and Updates ==

 * Training Instances: updated on date 26/01/2011;
 * Encoding: updated on date 26/01/2011;
 * Specification: updated on date 26/01/2011;

Appeared at 2nd ASP competition - 2009

Original Author: Neng-Fa Zhou, Affiliation: CUNY Brooklyn College

== Author(s) ==
 * Author: Francesco Calimeri 	
  * Affiliation: University of Calabria, Italy
 * Author: Maria Carmela Santoro 	
  * Affiliation: University of Calabria, Italy