A Knight's Tour on OCaml (when a Python fails to digest it)
Introduction
The story begins1 when my daughter's teacher, who is then busy grading the end-term examination papers, wanted to give the class some busy work. So the teacher asked the children to find a ``Knight's tour''---make a knight jump around on a chess board starting and ending at the same square and landing on each other square exactly once. Naturally, this problem landed on my doorstep at the end of the school day---the teacher happens to know that I do mathematics!I have heard that this problem has a solution but don't know one---typical Mathematician---stops at the point where ``solution exists''. So why not write a program to solve the problem? While the going is good, I could also use this opportunity to learn to use another programming language.
The quick and the dirty
Let's start by writing a program in a scripting language like Python---it is fun writing a program in a new language when you are reasonably sure that the code will not be longer than about a 100 lines!The key pseudo-code can be stated as follows:
extension of a partial solution =
if (Length of the partial solution is 64) then
if (the solution closes on itself) then
return the solution
else
return false since this is not a solution
else
for each position in available moves
that has not already been occupied
try extension of the new partial solution
obtained by extending the current solution
by this move
We then start with any position on the chess-board and find an extension of
it by 63 more moves.
This is programmed in Python quite easily. We use the Python ``workhorse'' data structure---the list. A partial solution is a list of positions which we think of as the sequence of moves.
def extend(soln):
if len(soln) == 64:
if soln[-1] in moves(soln[0]):
return soln
else:
return False
else:
for newpos in moves(soln[0]):
if newpos in soln:
continue
sol=extend([newpos]+soln)
if not sol:
continue
else:
return sol
return False
There is a nasty tail to this Python program fragment (the tail consists of 63
returns) but that should not be serious if we have enough stack space.
For us quicky-types ``optimization'' is a dirty word.
We also need to write routines that will generate the list of all possible moves at a given position.
If we represent positions on the board as pairs then the moves that a knight can make are given by
[(-1,-2), (-2,-1), (1,-2), (-2,1), (-1,2), (2,-1), (1,2), (2,1)]then the code fragment for this looks like
knightsmoves = [(-1,-2), (-2,-1), (1,-2), (-2,1), \
(-1,2), (2,-1), (1,2), (2,1)]
def add(pos1,pos2):
return (pos1[0] + pos2[0], pos1[1] + pos2[1])
def onboard(pos):
return (pos[0] >= 0) and
(pos[0] < 8) and
(pos[1] >= 0) and
(pos[1] < 8)
def moves(pos):
return [newpos for newpos in
[add(pos,move) for move in knightsmoves]
if onboard(newpos)]
Unfortunately, as it stands this program has no hope of producing an
answer in reasonable time. The reason is that we are trying all
possible moves in succession whereas we should be first going to
the square which cannot be easily reached from elsewhere. This means that
we need some new functions.
def filmoves(pos,soln):
return [newpos for newpos in moves(pos)
if not (newpos in soln)]
def compval(pos1,pos2,soln):
return len(filmoves(pos1,soln)) - len(filmoves(pos2,soln))
def sortedmoves(soln):
list = filmoves(soln[0],soln[1:])
list.sort(lambda x,y: compval(x,y,soln))
return list
The first function filters out moves already ``used up''.
The second uses this to compare two squares based on number of moves
currently available. The last function uses this comparison to sort the
moves. Note that we must also make a minor change to the extend function
to make it use sortedmoves (Warning: Only use sortedmoves
in the second call!).
According to authoritative sources (authoritative at least according to Google!) this particular algorithm was proposed by Warnsdorff in 1823. The above program is simple enough that we can ``see'' that it is correct and do not need any fancy verification procedure. Why then does is fail to give an answer when we start at the corner (0,0)? Surely a modern computer can beat a man born in 1823 in calculating things! What's wrong?!
If you don't believe me or believe that your computer is faster then just copy the code or type it in yourself and give it a whirl!
$ python
Python 2.3.4 (#2, Sep 24 2004, 08:39:09)
[GCC 3.3.4 (Debian 1:3.3.4-12)] on linux2
Type "help", "copyright", "credits" or "license" for
more information.
>>> from knights import *
>>> extend([(0,0)])
The program now appears to go sleep...!
Perhaps the reason is that Python is interpreted byte-code. A compiled language would be better. So we can set about downloading and installing psyco---a just-in-time native code compiler for Python. Meanwhile, we could try a ``real'' functional language---perhaps its implementation of lists is better. Maybe we can fit in time for a few functional programming tricks and see if tail-recursion is possible. (If you want a preview of the real answer, then jump to the Denouement.)
A humpy ride on OCaml
(I do happen to know that there is a more famous camel that appears more often in the pages of the Linux Gazette.) A nice candidate for our next choice of language is OCaml (this is also talked about in an article in an earlier Gazette). It is claimed that the optimizing native-code compiler for OCaml can beat even C in certain tasks. I have actually used the DVI previewer advi, the LATEX to HTML converter hevea2 and the file synchronizer unison; all these are written in OCaml and are quick and do the job well. Secondly, it would be a pain to sit and implement all the data structure management for lists in C just for this. So the knight must try to tour again---this time atop OCaml3. Just to clarify some of the differences
let plays the role of def and lists are constructed in
the form [a;b;c;d]. The syntax is also a little more arcane
but should be clear from the programs below.
While we are at it we can also introduce a tweak that avoids computing the length of a list all the time. Here is extend written in OCaml (the rec indicates a recursive definition):
let rec extend1 start len soln =
if (len == 64)
then
if List.mem start (moves (List.hd l))
then soln
else []
else
do_until (fun b -> extend1 start (len+1) (b::soln))
(sortedmoves soln);;
let extend start = extend1 start 1 [start];;
where do_until applies a function to a list until it produces an answer
or is empty:
let rec do_until f = function
| [] -> []
| h::t -> match f h with
| [] -> do_until f t
| answer -> answer;;
The | is used to introduce a pattern to match.
As before we need to define the functions that will produce the list of available moves.
let knightsmoves = [(-1,-2); (-2,-1); (1,-2); (-2,1);
(-1,2); (2,-1); (1,2); (2,1)];;
let add (a,b) (c,d) = (a+c,b+d);;
let onboard (a,b) =
(a >= 0) && (a < 8) &&
(b >= 0) && (b < 8);;
let moves pos =
List.filter (onboard)
(List.map (add pos) knightsmoves);;
let filmoves pos soln =
List.filter (fun b -> not (List.mem b soln)) (moves pos);;
let compval soln pos1 pos2 =
(List.length (filmoves pos1 soln)) -
(List.length (filmoves pos2 soln));;
let sortedmoves soln =
List.sort (compval soln)
(filmoves (List.hd soln) (List.tl soln));;
As you can see the ``pattern matching''-way of defining things in OCaml
really simplifies definitions.
We can string all these together - with the caveat that one must define a term before using it. So the later definitions have to come before the earlier ones. Programming languages which require declarations to come in order are best programmed ``bottom-up'' unless one can sort out all the details in one's head before putting a finger to the keyboard.
Now one can run the program by entering the interpreted mode of OCaml
$ ocaml
Objective Caml version 3.08.2
# #use "knights.ml";;
val knightsmoves : (int * int) list =
[(-1, -2); (-2, -1); (1, -2); (-2, 1); (-1, 2); (2, -1); (1, 2);
(2, 1)]
val add : int * int -> int * int -> int * int = <fun>
val onboard : int * int -> bool = <fun>
val moves : int * int -> (int * int) list = <fun>
val filmoves : int * int -> (int * int) list -> (int * int) list
= <fun>
val compval : (int * int) list -> int * int -> int * int -> int =
<fun>
val sortedmoves : (int * int) list -> (int * int) list = <fun>
val do_until : ('a -> 'b list) -> 'a list -> 'b list = <fun>
val extend1 : int * int -> int -> (int * int) list -> (int * int)
list = <fun>
val extend : int * int -> (int * int) list = <fun>
# extend (0,0)
But then the system goes to sleep as before .... The whole reason
for trying OCaml was to compile the code in the hope of a faster
response! So we need to run the native code compiler.
Before we do that however we need to have some way to do input and output, so a little more programming is involved. Our program produces output as a list of moves in order, what we want to output is the position of each square in this list. Since output happens only once we don't need to be particularly efficient.
let rec indexadd n pos soln =
match (List.hd soln) with
| pos -> n
| _ -> indexadd (n-1) pos (List.tl soln);;
let index pos soln = indexadd 64 pos soln;;
let printsoln soln =
(* Print the top line *)
for i = 1 to 8 do
Printf.printf "-----";
done;
Printf.printf "-\n";
for i = 0 to 7 do
for j = 0 to 7 do
Printf.printf "| %2i " (index (i,j) soln);
done;
Printf.printf "|\n";
(* Print a line below *)
for j = 1 to 8 do
Printf.printf "-----";
done;
Printf.printf "-\n";
done;;
Finally, the input procedure. For some strange reason OCaml uses !pointer to reference the contents - so the ! sign below is not
a ``not''.
if (!Sys.interactive)
then
(* If we are loaded in the interpreter do nothing *)
()
else
if (Array.length Sys.argv) > 2
then
print_soln
(extend
(int_of_string Sys.argv.(1), int_of_string Sys.argv.(2))
)
else
Printf.printf "Usage: %s x y\n" (Sys.argv.(0));;
Now we are all set. The compilation
$ ocamlopt -o knights knights.ml
produces a standalone program knights. So here goes
$ ./knights 0 0...and nothing happens!
Again, if you don't believe me, or you believe your computer is faster, you can download the OCaml source, compile it, and try it for yourself!
Denouement
Home for the day and I don't have OCaml on my home machine so I wrote the program afresh in Python. This time I felt too lazy to type in the knights moves again so I added:
knightsmoves = [((-1)**y*(1+x), (-1)**z*(2-x)) \
for x in [0,1] \
for y in [0,1] \
for z in [0,1]]
When I ran the program again I got
$ python
Python 2.3.4 (#2, Sep 24 2004, 08:39:09)
[GCC 3.3.4 (Debian 1:3.3.4-12)] on linux2
Type "help", "copyright", "credits" or "license" for more
information.
>>> from knights import *
>>> extend([(0,0)])
[(2, 1), (0, 2), (2, 3), (4, 4), (6, 5),
(7, 7), (5, 6), (3, 5), (1, 4), (3, 3),
(5, 4), (4, 2), (3, 4), (4, 6), (2, 7),
(0, 6), (2, 5), (0, 4), (1, 6), (3, 7),
(4, 5), (5, 3), (6, 1), (7, 3), (5, 2),
(4, 0), (3, 2), (2, 4), (4, 3), (2, 2),
(1, 0), (3, 1), (5, 0), (7, 1), (6, 3),
(7, 5), (6, 7), (5, 5), (7, 4), (6, 6),
(4, 7), (2, 6), (0, 7), (1, 5), (0, 3),
(1, 1), (3, 0), (5, 1), (7, 0), (6, 2),
(4, 1), (6, 0), (7, 2), (6, 4), (7, 6),
(5, 7), (3, 6), (1, 7), (0, 5), (1, 3),
(0, 1), (2, 0), (1, 2), (0, 0)]
>>>
Surprise! Here is a solution at last!
At this point, a bell somewhere had gone ``dung''... and I wasn't sure it was OCaml that did it---perhaps it was the prunes!
Then my daughter came over and said she had followed the algorithm by hand and come up with a solution. Her solution started at the square (4,4) so I tried that with the knights program compiled with OCaml.
$ ./knights 4 4 ----------------------------------------- | 9 | 6 | 11 | 44 | 27 | 4 | 29 | 34 | ----------------------------------------- | 12 | 43 | 8 | 5 | 46 | 33 | 26 | 3 | ----------------------------------------- | 7 | 10 | 45 | 48 | 55 | 28 | 35 | 30 | ----------------------------------------- | 42 | 13 | 54 | 63 | 32 | 47 | 2 | 25 | ----------------------------------------- | 53 | 60 | 49 | 56 | 1 | 62 | 31 | 36 | ----------------------------------------- | 14 | 41 | 64 | 61 | 50 | 19 | 24 | 21 | ----------------------------------------- | 59 | 52 | 39 | 16 | 57 | 22 | 37 | 18 | ----------------------------------------- | 40 | 15 | 58 | 51 | 38 | 17 | 20 | 23 | -----------------------------------------I decided then to check the authoritative source via Google once more. What it really says is that Warnsdorff's algorithm is for a Hamiltonian path---a path that takes a knight through each square exactly once---it is not necessary to return to the starting square.
What my experience with these programs shows is that Warnsdorff's algorithm is can find a Hamiltonian circuit reasonably quickly in some cases. Perhaps unsurprisingly it's success depends on the order in which one looks at the moves of the knights. For example, the above Python code to generate knightsmoves actually gives
[(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]Perhaps a little more surprising (since the final solution is circular) is the fact that the running time depends on the starting point. Indeed I got running times of a few milliseconds, a few seconds and a few hours (one process has been running for more than a couple of days!) for different inputs to the same program!
This may be rather typical of ``hard'' problems. There are a number of ``cheap'' instances and a number of truly ``hard'' instances but this distinction depends on where one starts---pure dumb luck decides whether one can solve the problem or not. (Actually it appears that the knights tour is not really a ``hard'' problem as one increases the size of the board (see Exercise 4, just below).)
Exercises
Here are some things that suggest themselves:- Try to find some real way to prove that the Python is better than OCaml or vice versa. Or more generally settle the great wars between functional and procedural programming!
- Try to randomize the choice from amongst the lowest valency vertices if there is more than one. This may result in shorter average times for all starting points.
- Try to add an extra weight to ensure that vertices further away from the start are taken up sooner than other vertices of the same valency. Perhaps this will be more efficient.
- There is apparently a better algorithm than Warnsdorff's for the Hamiltonian circuit. Find it and implement it.
Afterword
What does this article have to do with Linux or the Gazette? In a way, it is only due to the emergence of GNU and Linux that we have an opportunity to program in a wonderful plethora of languages. At the same the time the article above could be fit into one of the ``Foolish Things We do With Our Computers'' series or even in a new series called ``Nasty Things Our Computers Do To Us''!- 1
- . In case you are wondering what this talk has to do with Linux or the Gazette my justification is in the AfterWord, just above.
- 2
- . This HTML file has been converted using the TeX source and Hevea
- 3
- . Apparently, the idea of Python programs (and programmers!) turning to OCaml is not one that occurred to me alone.
This document was translated from LATEX by HEVEA.
![[BIO]](../gx/authors/kapil.jpg)
Kapil Hari Paranjape has been a ``hack''-er since his punch-card days.
Specifically, this means that he has never written a ``real'' program.
He has merely tinkered with programs written by others. After playing
with Minix in 1990-91 he thought of writing his first program---a
``genuine'' *nix kernel for the x86 class of machines. Luckily for him a
certain L. Torvalds got there first---thereby saving him the trouble
(once again) of actually writing code. In eternal gratitude he has spent
a lot of time tinkering with and promoting Linux and GNU since those
days---much to the dismay of many around him who think he should
concentrate on mathematical research---which is his paying job. The
interplay between actual running programs, what can be computed in
principle and what can be shown to exist continues to fascinate him.
