The Problem of the Knight

A Fast and Simple Algorithm

Arnd Roth
Max-Planck-Institut fuer Medizinische Forschung
Postfach 10 38 20, D-69028 Heidelberg, Germany
roth@sunny.mpimf-heidelberg.mpg.de

Introduction

More than 200 years ago, Leonhard Euler posed the following problem:
   Given a chessboard of n times n squares, is it possible to find a path for the knight that
   touches every square exactly once in succession?
   This has been a question of interest for a long time [2]. It is easy to think of a search
   procedure that must find a path if there is one (and it turns out that for n >= 5, there
   are many): backtracking. The knight moves along as far as possible, and if it comes
   into a blind alley, it takes back some of its steps in order to follow another direction.
   
   The problem is that for big chessboards, backtracking is very slow. So Warnsdorff [3]
   proposed an algorithm that should find a path without taking back any step. At each
   position of the knight, a rating of its successors is computed. Successors of a
   position are those squares that have not been touched yet and can be reached by one 
   knight's jump from this position. The rating is highest for the successor whose number
   of successors is least. That way, squares tending to be isolated are visited first and
   therefore prevented from being isolated. The time needed for this algorithm grows
   about linearly with the number of squares of the chessboard, but unfortunately the
   computer experiment (which was not available to Warnsdorff) shows that at least
   for chessboards bigger than 76 times 76 squares, it also runs into blind alleys. For
   smaller boards, it solves the problem quite nicely.
   
   Recently, another linear time algorithm has been discovered and proved to solve the
   problem for all n >= 5 [1]. It works by decomposition of the chessboard into smaller
   chessboards (not necessarily square ones) for which explicit solutions are known.
   But this algorithm is quite complicated because it has to deal with many special
   cases.
   
   So the question remains: is there an algorithm, comparable to Warnsdorff's in
   simplicity, that definitely solves the problem? So far, nobody knows. One might try
   to improve Warnsdorff's rating scheme. It has the unpleasant property that it
   introduces some arbitrariness if there is more than one successor with least number
   of successors. To amend this, I add the rule that in this case, the successor with
   largest euclidean distance to the center of the chessboard is chosen. The introduction
   of this global criterion substantially reduces the number of blind alleys: now it first
   occurs on a 428 times 428 chessboard, and the "probability" to run into one is less
   than one precent for all chessboards smaller than 2000 times 2000 squares. (All
   this assumes that the starting point is in a corner of the board.)
   
   Mathematica was chosen for the implementation of the improved version of
   Warnsdorff's algorithm because of its list processing capabilities. The implementation
   isn't optimized for speed but for brevity and readability. Chessboards up to 100 times
   100 can be calculated in reasonable time on most workstations.
   
   References:
   [1] Conrad, A., Hindrichs, T., Morsy, H. & Wegener, I., Solution of the Knight's
   Hamiltonian Path Problem on Chessboards, Discr. Appl. Math., to appear (1992)
   [2] Kraitchik, M., Mathematical Recreations, Chapter 11, The Problem of the Knight
   (Allen & Unwin, London, 1966)
   [3] Warnsdorff, H. C., Des Roesselsprungs einfachste und allgemeinste Loesung
   (Schmalkalden, 1823)

Implementation

(* Improved Warnsdorff's Algorithm for the Problem of  *)
(* the Knight                                          *)
(* Mathematica 2.2 Version Copyright 1992-93 Arnd Roth *)

knightJumps = {{2, -1}, {1, -2}, {-1, -2}, {-2, -1},
               {-2, 1}, {-1, 2}, {1, 2  }, {2, 1  }};

successors[s_, n_, position_] :=
Block[{moves, onBoard},
      moves = Map[position + # &, knightJumps];
      (* moves over the edge of the chessboard are *)
      (* invalid *)
      onBoard = Select[moves, And @@ Thread[
                              {0, 0} < # <= {n, n}] &];
      Select[onBoard, s[[Sequence @@ #]] == 0 &]
]

numberOfSuccessors[s_, n_, position_] :=
Length[successors[s, n, position]]

mina[s_, n_, position_] :=
(* successor(s) with least number of successors *)
Block[{localSuccessors, localNumbersOfSuccessors,
       minimum},
      localSuccessors = successors[s, n, position];
      localNumbersOfSuccessors =
      Map[numberOfSuccessors[s, n, #] &,
          localSuccessors];
      minimum = Min[localNumbersOfSuccessors];
      localSuccessors[[Flatten[Position[
      localNumbersOfSuccessors, minimum]]]]
]

mabst[destination_, successorlist_] :=
(* successor(s) with greatest distance from *)
(* destination *)
Block[{vectors, distances, maximum},
      vectors = Map[destination - # &, successorlist];
      distances = Map[# . # &, vectors];
      maximum = Max[distances];
      successorlist[[Flatten[Position[
      distances, maximum]]]]
]

improvedWarnsdorff[n_] :=
(* main program *)
Block[{s, destination, position, localMina},
      (* initialize chessboard s *)
      (* s[[x, y]] == 0  ==> square (x, y) is *)
      (* untouched. *)
      (* in the end, s contains the step numbers *)
      (* at which every square was visited *)
      s = Table[0, {n}, {n}];
      (* path should end near the following *)
      destination =
      {Round[n / 2] - 1 / 2, Round[n / 2] - 1 / 2};
      (* starting point in the corner of the board *)
      position = {1, 1};
      s[[1, 1]] = 1;
      Do[
         localMina = mina[s, n, position];
         If[Length[localMina] == 0,
            Print["Blind alley"];
            (* algorithm failed *)
            Break[]
         ];
         position = If[Length[localMina] == 1,
                       First[localMina],
                       First[mabst[destination,
                                   localMina]]
                    ];
         s[[First[position], Last[position]]] =
         stepNumber,
      {stepNumber, 2, n n}];
      s
]

Examples

s = improvedWarnsdorff[8];
MatrixForm[s]
ListDensityPlot[s]

First[Timing[s = improvedWarnsdorff[60];]]
ListDensityPlot[s]

s = improvedWarnsdorff[180];
ListDensityPlot[s, Mesh -> False]