Knight's tour is one of those chess problems I always wanted to solve, but I never had enough patience. Now, thanks to Prolog, it is easy--I just have to write a simple program. And, yes, I am completely aware of the fact that solving it by myself probably would take me less time; however, at the moment I don't own a chess board (without the board it is no fun) and I feel this is a good way of improving my Prolog skills. So, here we go.
To solve the problem to visit all the squares on the board, without any repetitions, moving by horse-jumps (that seems the best way of calling the movement of the knight). The starting square and size of the board are given as parameters.
Lets represent a square on the board by a pair of numbers divided by a slash.
First of all, the way the knight moves:
boardX(8).
boardY(8).
knight(X/Y,X1/Y1) :-
boardX(BoardX),
boardY(BoardY),
(
(X1 is X+2 ;
X1 is X-2),
(Y1 is Y+1 ;
Y1 is Y-1)
;
(Y1 is Y+2 ;
Y1 is Y-2),
(X1 is X+1 ;
X1 is X-1)
),
X1 >= 1, X1 =< BoardX,
Y1 >= 1, Y1 =< BoardY.
The dimensions of the board aren't hardcoded in case we want to solve the puzzle on a nonstandard board, eg. 4x8.
knights_way([_/_],_).
knights_way([First,Second|Rest],Visited) :-
knight(First,Second),
\+member(Second,Visited), % No repetitions, please!
knights_way([Second|Rest],[Second|Visited]).
knights_tour_1(X,N) :-
length(X,N),
X=[1/1|_],
knights_way(X,[]).
knights_tour(X) :-
N is BoardX*BoardY,
knights_tour_1(X,N).
Now, this seems pretty easy (although writing it properly took me some time--I don't know Prolog very well, yet). However, not everything in life is as easy as it seems. When you try to run knights_tour on your computer, you won't get an answer, unless your computer is very fast, or you are very patient and long-lived. Why? Let's compare the times:
?- time(knights_tour_1(X,59)).
% 46,797 inferences, 0.02 CPU in 0.01 seconds (141% CPU, 2339850 Lips)
X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]
?- time(knights_tour(X,60)).
% 1,677,669 inferences, 0.50 CPU in 0.50 seconds (100% CPU, 3355338 Lips)
X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]
?- time(knights_tour_1(X,61)).
% 92,595,863 inferences, 27.43 CPU in 28.15 seconds (97% CPU, 3375715 Lips)
X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]
?- time(knights_tour_1(X,63)).
C-c C-c
Action (h for help) ? a
abort
% 4,550,510,155 inferences, 1345.57 CPU in 1418.71 seconds (95% CPU, 3381846 Lips)
% Execution Aborted
It seems clear, that the number of inferences is growing very fast, or at least faster than we can afford. That shouldn't be a big surprise: the knight has on average from 2 to 8 possible moves--the size of the solution space we have to search grows exponentially. Blind search just won't do.
So, what we now need is a good heuristic. Fortunately, there's such a heuristic, and it has been developed in 1832 by H.C. von Warnsdorf, which says that the best available square is the one which is available from the least unvisited squares (see
here and
here). It is said not to work very well for boards bigger than 76x76, but I don't think it's a very big deal.
heuristic(X/Y, Visited, N) :-
findall(A,knight(X/Y,A),Possible),
subtract(Possible,Visited,List),
length(List,N). % I know this may be incorporated to the next predicate, but somehow I feel that splitting it apart is a good thing.
better_heuristic(Visited,A,B) :-
heuristic(A,Visited,HA),
heuristic(B,Visited,HB),
HA =< HB.
A crucial part of our program will be sorting the list of available moves using the heuristic. At first I thought this wouldn't be very important--there were going to be at most 7 elements in the list I wanted to sort--so I wrote a quite lousy linear insert sort. However, this turned to be a bad idea: the whole thing just worked too slow. Changing it to quicksort gave my program a big speed boost (practically, made it work).
Basically, I'm against rewriting things like sorting functions, if there are functions for doing the same provided by the interpreter, written in C and usually much faster. However, SWI-Prolog's sort/2 is lame: it just sorts a list of numbers. And I am used to the Lisp approach, which is a lot more flexible: you are supposed to provide a function that you want to use to compare the elements as an argument to the sorting function.
To my very surprise, implementing such a Lisp-style sorting function in Prolog using call wasn't tricky nor difficult. Of course, there are no lambda-expressions in Prolog, so the final effect is a bit crude: you have to very careful when planning the order of arguments in your predicates. However, this is acceptable--nothing is perfect. As far as I know, this isn't Prolog mainstream, and that's a pity. I feel it's the most elegant solution.
split(Fun,Pivot,[H|Tail],[H|Positives], Negatives) :- % Fun for function. We all know that fuctions are funny.
call(Fun,Pivot,H),!,%H > Pivot,!,
split(Fun,Pivot,Tail, Positives, Negatives).
split(Fun,Pivot,[H|Tail], Positives, [H|Negatives]) :-
call(Fun,H, Pivot),
split(Fun,Pivot,Tail, Positives, Negatives).
qsort(_,[],[]).
qsort(Fun,[Pivot|List],Sorted):-
split(Fun,Pivot, List, Bigger, Smaller),
qsort(Fun,Bigger,NewBigger),
qsort(Fun,Smaller,NewSmaller),
append(NewSmaller, [Pivot|NewBigger], Sorted).
Now, lets put everything together:
hknight(A/B,X,Visited) :- % the `h' is for `heuristic.'
findall(W, knight(A/B, W), Moves),
qsort(better_heuristic(Visited), Moves, SortedMoves),
member(X, SortedMoves). % member chooses the elements preserving the order.
hknights_way([_/_],_).
hknights_way([First,Second|Rest],Visited) :-
hknight(First,Second,Visited),
\+member(Second,Visited),
hknights_way([Second|Rest],[Second|Visited]).
hknights_tour_1(X,N) :-
length(X,N),
X=[1/1|_],
hknights_way(X,[1/1]).
hknights_tour(X) :-
N is BoardX*BoardY,
hknights_tour_1(X,N).
And voilà! We have our problem solved. An example solution:
[ 1, 16, 51, 34, 3, 18, 21, 36]
[50, 33, 2, 17, 52, 35, 4, 19]
[15, 64, 49, 56, 45, 20, 37, 22]
[32, 55, 44, 63, 48, 53, 42, 5]
[61, 14, 57, 54, 43, 46, 23, 38]
[28, 31, 62, 47, 58, 41, 6, 9]
[13, 60, 29, 26, 11, 8, 39, 24]
[30, 27, 12, 59, 40, 25, 10, 7]
I updated this post on Fri Oct 27, 5:14 PM in order to incorporate some useful suggestions made by Daan Fierens. Thank you!
