next up previous
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 tex2html_wrap_inline451 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