Closed Knight's Tour in Prolog
Prolog code: knight.pl
uses CLP(ℤ) constraints
to model the problem. In particular,
the circuit/1 constraint is used to describe a
Hamiltonian circuit of the following graph:
For example, in the case of a 6×6 board, the underlying
graph looks as follows:
- one node per board position
- one edge between those nodes that can be reached via
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:
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