The Problem of the Knight
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
Max-Planck-Institut fuer Medizinische Forschung
Postfach 10 38 20, D-69028 Heidelberg, Germany
roth@sunny.mpimf-heidelberg.mpg.de
Introduction
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)
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
Implementation
In[1]:=
(* 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
]
(* 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
Examples
In[1]:=
s = improvedWarnsdorff[8];
MatrixForm[s]
ListDensityPlot[s]
MatrixForm[s]
ListDensityPlot[s]
Out[1]=
Out[1]=
In[2]:=
First[Timing[s = improvedWarnsdorff[60];]]
ListDensityPlot[s]
ListDensityPlot[s]
Out[2]=
Out[2]=
In[3]:=
s = improvedWarnsdorff[180];
ListDensityPlot[s, Mesh -> False]
ListDensityPlot[s, Mesh -> False]
Out[3]=