...making Linux just a little more fun!

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 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 moveWe 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 FalseThere 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

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 listThe 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

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.)

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

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

`!`

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.mlproduces a standalone program

$ ./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!

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

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).)

- 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.

- 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 L^{A}T_{E}X byH^{E}V^{E}A.

*
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.
*