Shortcuts
 
Sitemap Sitemap
Comment Contact
Newsletter Newsletter
Store Store
Books
Syndication Features
Gallery Gallery
E-cards
E-cards
Games Games

eureka!!!
corner

Books to delight
your mind!

corner top left

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

  line  

Introduction
Knight chess piece  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?

Knight tour_1gif

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

Knight tour_3gif

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.

Knight tour_4gif

line

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.

line
Problems 1 and 2

How can the knight visit each square on this board exactly once?

Knight tour_6gif

line
Problems 3 and 4
How can the knight visit each square on this board exactly once?

Knight tour_8gif

line
Problems 5 and 6
How can the knight visit each square on this board exactly once?

Knight tour_10gif

line
Problems 7 and 8
How can the knight visit each square on this board exactly once?

Knight tour_12gif

line
Problems 9 and 10
How can the knight visit each square on this board exactly once?

Knight tour_14gif

line
Problems 11 and 12
How can the knight visit each square on this board exactly once?

Knight tour_16gif

line
Graphs
Roll-over the selections below to see the related graphs.
Graphs made from Problems 1 and 2
Graphs made from Problems 3 and 4
Graphs made from Problems 5 and 6
Graphs made from Problems 7 and 8
Graphs made from Problems 9 and 10
Graphs made from Problems 11 and 12

Knight tour_24gif

line
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
arrow The Knight's Tour An Extremely Simple Solution
arrow The Knight's Tour after Martin Gardner
arrow Knight’s tours using a neural network

arrow Knight's Tour demonstration
arrow 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!

 

transparent gif
facebook Follow us on Facebook | comment Report any error, misspelling or dead link
Archimedes' Lab | How to contact us | italian flag Come contattarci | francais flag Comment nous contacter
line
About Us | Sponsorship | Press-clippings | Cont@ct | ©opyrights | Link2us | Sitemap
© Archimedes' Lab | Privacy & Terms | The web's best resource for puzzling and mental activities
spacer spacer corner right bottom