welcome: please sign in
location: Diff for "KnightTour"
Differences between revisions 1 and 7 (spanning 6 versions)
⇤ ← Revision 1 as of 2012-11-05 14:28:59 →
Size: 2357
Editor: PatrikSchneider
Comment: Knight Tour added
← Revision 7 as of 2013-02-22 09:39:09 → ⇥
Size: 2964
Editor: FrancescoCalimeri
Comment:
Deletions are marked like this. Additions are marked like this.
Line 3: Line 3:
<<TableOfContents>>
Line 7: Line 6:
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. Find a tour for the knight piece that starts at any square, travels
all squares but the forbidden ones (representing holes on the board),
and comes back to the origin, following the rules of chess and
Line 11: Line 13:
 * '''Input''': {{{size/1, givenmove/4}}}  * '''Input''': {{{size/1, forbidden/2}}}
Line 16: Line 18:
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. The input file contains one atom {{{size(N)}}}, which states that the chess board size is N*N and a number of atoms {{{forbidden(X1,Y1)}}}. 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. Each square can thus be represented by a unique pair of coordinates.
Line 21: Line 23:

{{{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. 		{{{
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, no move ends onto a forbidden square.
Line 28: Line 30:
Input: A given input might be:
Line 30: Line 32:
size(8). givenmove(7,5,8,7). givenmove(1,7,3,6). size(9).

forbidden(1,9). forbidden(2,9). forbidden(3,9). forbidden(4,9). forbidden(5,9). forbidden(6,9). forbidden(7,9). forbidden(8,9). forbidden(9,9).

forbidden(9,1). forbidden(9,2). forbidden(9,3). forbidden(9,4). forbidden(9,5). forbidden(9,6). forbidden(9,7). forbidden(9,8). forbidden(9,9).
Line 32: Line 38:
Output: Resulting in the following output:
Line 34: Line 40:
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). 		move(1,1,2,3). move(1,2,3,3). move(1,3,3,4). move(1,4,3,5). move(1,5,3,4). move(1,6,3,5). move(1,7,3,8). move(1,8,2,6). move(2,1,3,3). move(2,2,1,4). move(2,3,3,5). move(2,4,4,3). move(2,5,3,3). move(2,6,3,8). move(2,7,3,5). move(2,8,4,7). move(3,1,4,3). move(3,2,5,1). move(3,3,5,2). move(3,4,2,6). move(3,5,1,4). move(3,6,4,8). move(3,7,5,8). move(3,8,5,7). move(4,1,3,3). move(4,2,3,4). move(4,3,6,2). move(4,4,2,3). move(4,5,6,4). move(4,6,5,8). move(4,7,2,6). move(4,8,6,7). move(5,1,7,2). move(5,2,6,4). move(5,3,3,4). move(5,4,4,6). move(5,5,4,3). move(5,6,3,5). move(5,7,4,5). move(5,8,4,6). move(6,1,7,3). move(6,2,4,3). move(6,3,7,5). move(6,4,8,5). move(6,5,4,6). move(6,6,4,5). move(6,7,4,8). move(6,8,4,7). move(7,1,5,2). move(7,2,5,1). move(7,3,8,5). move(7,4,6,2). move(7,5,6,7). move(7,6,6,4). move(7,7,8,5). move(7,8,5,7). move(8,1,6,2). move(8,2,7,4). move(8,3,6,4). move(8,4,7,2). move(8,5,7,3). move(8,6,7,4). move(8,7,7,5). move(8,8,6,7).
Line 40: Line 42:

Additional sample instances: [[https://www.mat.unical.it/aspcomp2013/files/links/samples/knight_tour-sample.zip|download]]

== Problem Peculiarities ==

'''Type''': Search
'''Competition''': System Track
Line 41: Line 51:
 * 2013 02 22: update description - Now the chessboard might have holes, and no mandatory moves are given.

Knight Tour

Problem Description

Find a tour for the knight piece that starts at any square, travels all squares but the forbidden ones (representing holes on the board), and comes back to the origin, following the rules of chess and

Predicates

  • Input: size/1, forbidden/2

  • 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 forbidden(X1,Y1). 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. Each square can thus 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, no move ends onto a forbidden square.

Example(s)

A given input might be: 

size(9).

forbidden(1,9). forbidden(2,9). forbidden(3,9). forbidden(4,9). forbidden(5,9). forbidden(6,9). forbidden(7,9). forbidden(8,9). forbidden(9,9).

forbidden(9,1). forbidden(9,2). forbidden(9,3). forbidden(9,4). forbidden(9,5). forbidden(9,6). forbidden(9,7). forbidden(9,8). forbidden(9,9).

Resulting in the following output: 

move(1,1,2,3). move(1,2,3,3). move(1,3,3,4). move(1,4,3,5). move(1,5,3,4). move(1,6,3,5). move(1,7,3,8). move(1,8,2,6). move(2,1,3,3). move(2,2,1,4). move(2,3,3,5). move(2,4,4,3). move(2,5,3,3). move(2,6,3,8). move(2,7,3,5). move(2,8,4,7). move(3,1,4,3). move(3,2,5,1). move(3,3,5,2). move(3,4,2,6). move(3,5,1,4). move(3,6,4,8). move(3,7,5,8). move(3,8,5,7). move(4,1,3,3). move(4,2,3,4). move(4,3,6,2). move(4,4,2,3). move(4,5,6,4). move(4,6,5,8). move(4,7,2,6). move(4,8,6,7). move(5,1,7,2). move(5,2,6,4). move(5,3,3,4). move(5,4,4,6). move(5,5,4,3). move(5,6,3,5). move(5,7,4,5). move(5,8,4,6). move(6,1,7,3). move(6,2,4,3). move(6,3,7,5). move(6,4,8,5). move(6,5,4,6). move(6,6,4,5). move(6,7,4,8). move(6,8,4,7). move(7,1,5,2). move(7,2,5,1). move(7,3,8,5). move(7,4,6,2). move(7,5,6,7). move(7,6,6,4). move(7,7,8,5). move(7,8,5,7). move(8,1,6,2). move(8,2,7,4). move(8,3,6,4). move(8,4,7,2). move(8,5,7,3). move(8,6,7,4). move(8,7,7,5). move(8,8,6,7).

Additional sample instances: download

Problem Peculiarities

Type: Search Competition: System Track

Notes and Updates

  • 2013 02 22: update description - Now the chessboard might have holes, and no mandatory moves are given.

Author(s)

  • Author: Francesco Calimeri
    • Affiliation: University of Calabria, Italy
  • Original Author: Neng-Fa Zhou
    • Affiliation: CUNY Brooklyn College

ASP Competition 2013: KnightTour (last edited 2013-03-14 22:26:43 by FrancescoCalimeri)