# 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]

In[2]:=

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

ListDensityPlot[s]

ListDensityPlot[s]

In[3]:=

s = improvedWarnsdorff[180];

ListDensityPlot[s, Mesh -> False]

ListDensityPlot[s, Mesh -> False]