Shortcuts

 Sitemap Contact Newsletter Store Books Features Gallery E-cards Games

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

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 L-shaped 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 're-entrant' 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 al-arbab al-'aqulfi'sh-shatranj al-manqul" (The delight of the intelligent, a description of chess) and came from al-Adli ar-Rumi, a professional chess player who lived in Baghdad around 840 AD. The pattern of a Knight's Tour on a half-board 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 re-entrant (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 Roll-over 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!

 Related Links Share your thoughts The Knight's Tour An Extremely Simple Solution The Knight's Tour after Martin Gardner Knight’s tours using a neural network Knight's Tour demonstration An animated Knight's Tour for you to download. You're encouraged to expand and improve the articles featured on this page. Send us your comments that you would like considered for publication. Please include your name and location. Thanks!