


Shortcuts 





New
Knight's Tour Puzzles and Graphs


Some
neat variants of the famous Knight's Tour

by Yuya Kakoi, Naoki Saida, Kazuki Takeshima, Yuma Kunimori,
Takashi Kajimoto, Hiroshi Matsui, Toshiyuki Yamauchi,
Naoyuki Totani and Ryohei
Miyadera.
Adaptated by Gianni A. Sarcone
Knight's
Tour: Problema del cavallo (it), Problème du
cavalier (fr), Problema del caballo (sp), Problema do cavalo
(por), Springerproblem (ger), חידת מסע הפרש (he), 騎士巡邏 (ch), ナイト・ツアー (jap).




Introduction
The
'knight'
(♘ ♞, colloquially, horse) is a
piece in the game of chess, representing a knight. But
unlike the other chess
pieces, it doesn't move in a straight line but makes Lshaped
moves, jumping over anything in its way to reach
an empty square on a chessboard. For example, a knight
can move two squares forward, then one square sideways,
or it can move one square forward, then two squares sideways.
Traditionally
the "Knight's Tour" is a
sequence of moves done by a knight on a chessboard.
The knight is placed on an empty chessboard and, following
the rules
of chess, must visit each square exactly
once. There are several billion solutions
to the problem, of which about 122,000,000 have the
knight finishing on a square which is just a move away
from the starting square. Such a tour is described
as 'reentrant' or 'closed'.
The Knight's Tour problem is an instance of the more general Hamiltonian
path problem in graph theory. The problem of getting a closed Knight's
Tour is similarly an instance of the Hamiltonian cycle problem.
People
have been entertaining themselves with these path problems
for centuries. The earliest recorded example of a Knight's
Tour on the ordinary 8x8 board is described in an arabic
manuscript with the title "Nuzhat alarbab al'aqulfi'shshatranj almanqul" (The
delight of the intelligent, a description of chess)
and came from alAdli arRumi, a professional
chess player who lived in Baghdad around 840 AD. The
pattern of a Knight's Tour on a halfboard has been
presented in verse form (as a literary constraint)
in the highly stylized Sanskrit poem Kâvyâlankâra (meaning:
The ornaments of poetry) written by the 9th century
Kashmiri poet Rudrata.
Since
it is possible to define a Knight's Tour on any grid
pattern, we will then use in our variants described
below some particular boards, instead of the usual
chessboard. Interestingly, we can draw a graph from
the path of a Knight's Tour: each vertex of the graph
represents then a square of the board and each edge,
a knight's move. Some knight graphs can be considered
works of art!
Example
How
can the knight visit each square on the following board
exactly once?
Answer
The numbers in the squares represent
the sequence of the moves. Note that the following tour,
which starts from 1 and goes to 36, is reentrant (closed).
Graph
made from the board
By using the above board pattern which
consists of 36 squares we can draw a nice graph. These
36 squares represent, in fact, 36 vertexes of the graph
(in red, see the diagram below). The network (in blue)
shows all the moves of the knight to complete the tour
according to the chess rules.
Solve
them all!
Our objective is to make you solve some problems of the Knight's
Tour and enjoy at the same time the visual elegance of the graphs made from these
problems. The problems presented here are not very difficult, but they are instructive
for those who want an introduction to path problems.
Print this page, take a pencil and try to solve the puzzles 1 to
12 below: fill ALL the squares of each pattern with consecutive numbers representing
the sequence of the knight's moves to complete the tour.
Problems 1 and 2
How can the knight visit each square on
this board exactly once?
Problems 3 and 4
How can the knight visit
each square on this board exactly once?
Problems 5 and 6
How can the knight visit each square on this board
exactly once?
Problems 7 and 8
How can the knight visit
each square on this board exactly once?
Problems 9 and 10
How can the knight visit
each square on this board exactly once?
Problems 11 and 12
How can the knight visit
each square on this board exactly once?
Graphs
Rollover
the selections below to see the related graphs.

Taking inspiration from the examples shown above you
can create your own Knight's Tour puzzles and graphs.
Mail us yours creations, the best ones will be published on this
page!

