Next: Kirkman's School Girl Problem Up: EXAMPLES Previous: List Reverse

## Knight Tour

Resources can be used to represent constrains.

Let us consider a problem of finding a Hamilton path of a given graph. In Hamilton path, all vertices are visited exactly once. This constraint can be represented easily by using resources for vertices. Visited vertices are removed during the execution, and the program succeeds only when all vertices are visited exactly once.

The following program finds a tour of Knight (a chess piece) on a board.

```knight5(Tour) :-
(k(1,1), k(1,2), k(1,3), k(1,4), k(1,5),
k(2,1), k(2,2), k(2,3), k(2,4), k(2,5),
k(3,1), k(3,2), k(3,3), k(3,4), k(3,5),
k(4,1), k(4,2), k(4,3), k(4,4), k(4,5),
k(5,1), k(5,2), k(5,3), k(5,4), k(5,5)) -<>
tour(1, 1, Tour).

tour(I, J, [(I,J)|Tour]) :-
k(I, J), next(I, J, I1, J1), tour(I1, J1, Tour).
tour(I, J, [(I,J)]) :-
k(I, J).

next(I, J, I1, J1) :- I1 is I-2, J1 is J-1.
next(I, J, I1, J1) :- I1 is I-2, J1 is J+1.
next(I, J, I1, J1) :- I1 is I-1, J1 is J-2.
next(I, J, I1, J1) :- I1 is I-1, J1 is J+2.
next(I, J, I1, J1) :- I1 is I+1, J1 is J-2.
next(I, J, I1, J1) :- I1 is I+1, J1 is J+2.
next(I, J, I1, J1) :- I1 is I+2, J1 is J-1.
next(I, J, I1, J1) :- I1 is I+2, J1 is J+1.
```

Naoyuki Tamura
Thu May 8 20:39:01 JST 1997