Skip to main content
Logo image

Problem Solving with Algorithms and Data Structures using Java The Interactive Edition

Section 7.11 The Knight’s Tour Problem

Another classic problem that we can use to illustrate a second common graph algorithm is called the knight’s tour. The knight’s tour puzzle is played on a chess board with a single chess piece, the knight. The object of the puzzle is to find a sequence of moves that allow the knight to visit every square on the board exactly once. One such sequence is called a tour. The knight’s tour puzzle has fascinated chess players, mathematicians, and now, computer scientists, for over a thousand years. The upper bound on the number of possible legal tours for an 8×8 chessboard is known to be 1.305×1035; however, there are even more possible dead ends. Clearly this is a problem that requires some real brains, some real computing power, or both.
Although researchers have studied many different algorithms to solve the knight’s tour problem, a graph search is one of the easiest to understand and program. Once again we will solve the problem using two main steps:
  • Represent the legal moves of a knight on a chessboard as a graph.
  • Use a graph algorithm to find a path of length rows×columns1 where every vertex on the graph is visited exactly once.
You have attempted 1 of 1 activities on this page.