Closed Knight's Tour in Prolog



Prolog code: knight.pl

Video: Knight's Tour


This solution uses CLP(ℤ) constraints to model the problem. In particular, the circuit/1 constraint is used to describe a Hamiltonian circuit of the following graph:
  1. one node per board position
  2. one edge between those nodes that can be reached via knight's moves.
For example, in the case of a 6×6 board, the underlying graph looks as follows:



You need Scryer Prolog. Start it with 
$ scryer-prolog knight.pl

Example queries that you can try: 

?- n_tour(N, Ts), maplist(label, Ts).

?- n_tour(N, Ts), maplist(label, Ts), print_tour(Ts).
To visualize solutions with Ghostscript, use: 
       $ scryer-prolog -g "show(6,[ff])" knight.pl | \
            gs -dNOPROMPT -g510x510 -r72 -q


Sample solutions for N = 6, 8, 12, 16:

6x6 board 8x8 board
12x12 board 16x16 board




Challenges: Find solutions for large boards. Find good labeling and allocation strategies. ...

Exercise: Modify the code so that it describes knight's tours that are not necessarily closed. Hint: Introduce a dummy node from which a tour may start.


More about Prolog: The Power of Prolog


Main page