welcome:

## Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

location: KnightTour

# 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.

## 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,1). move(1,3,3,2). move(1,4,3,3). move(1,5,2,7). move(1,6,2,4). move(1,7,3,6). move(1,8,2,6). move(2,1,1,3). move(2,2,4,3). move(2,3,4,4). move(2,4,1,2). move(2,5,3,7). move(2,6,3,8). move(2,7,4,8). move(2,8,1,6). move(3,1,5,2). move(3,2,1,1). move(3,3,2,1). move(3,4,1,5). move(3,5,1,4). move(3,6,5,5). move(3,7,1,8). move(3,8,1,7). move(4,1,2,2). move(4,2,5,4). move(4,3,5,1). move(4,4,2,5). move(4,5,6,6). move(4,6,3,4). move(4,7,2,8). move(4,8,5,6). move(5,1,7,2). move(5,2,7,1). move(5,3,4,1). move(5,4,7,3). move(5,5,7,6). move(5,6,3,5). move(5,7,4,5). move(5,8,4,6). move(6,1,5,3). move(6,2,7,4). move(6,3,4,2). move(6,4,8,5). move(6,5,8,6). move(6,6,8,7). move(6,7,7,5). move(6,8,4,7). move(7,1,8,3). move(7,2,8,4). move(7,3,8,1). move(7,4,8,2). move(7,5,6,3). move(7,6,8,8). move(7,7,5,8). move(7,8,5,7). move(8,1,6,2). move(8,2,6,1). move(8,3,6,4). move(8,4,6,5). move(8,5,7,7). move(8,6,7,8). move(8,7,6,8). move(8,8,6,7).`

## 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