About the Knight's Tour | Warnsdorff's Rule, Open and Closed Tours

An old puzzle

In the Kavyalankara, written by the Indian poet Rudrata in the 9th century, a verse is laid out on half a chessboard so that it can be read along the path of a knight. Leonhard Euler wrote the first mathematical study of the knight's tour in 1759, with ways to build tours and to turn them into closed ones.

A path through a graph

Think of each square as a point and each knight move as a line between two points. A knight's tour is then a path that visits every point exactly once, which mathematicians call a Hamiltonian path; a closed tour is a Hamiltonian cycle. For most networks such a path is very hard to find. The knight's network is generous: it has so many tours that a good rule finds one quickly.

Warnsdorff's rule

H. C. von Warnsdorff described his rule in 1823: always jump to the square that leaves the fewest onward moves. Squares along the edge have few neighbors, so the rule visits them early instead of leaving them stranded. When two squares tie, a choice is needed, and an unlucky choice can still get the knight stuck. In the app, the gold numbers mark the squares the rule would pick.

Searching with backtracking

Solve follows Warnsdorff's order but does not trust it blindly. It searches depth first, and as soon as an unvisited square can no longer be reached it abandons that branch and tries the next move. On boards up to 10×10 it usually finds a tour at once. When your own path has walled the knight in, it backs up a few moves first.

Colors and closed tours

Every knight move changes the color of the square. On an odd board such as 5×5 there is one more square of the corner color than of the other, so a tour must start and end on the corner color. A closed tour is impossible there, because a loop that alternates colors has as many squares of each. On even boards closed tours exist from 6×6 up.

Try it in PictorX

Open the Knight's Tour and click a square to start. The highlighted squares are the legal jumps, the gold number is Warnsdorff's choice, and the board keeps the order of your moves. Size sets the board from 5×5 to 10×10, Closed tour asks Solve for a loop, and Undo takes back any move. Save the finished path as a PNG.

Frequently asked questions

Who first studied the knight's tour?

Tours were known long before anyone studied them mathematically. Leonhard Euler wrote the first mathematical treatment in 1759, and Warnsdorff gave his rule in 1823.

Is there a tour on every board?

Square boards from 5×5 up have open tours, and the even ones from 6×6 up also have closed tours. Boards of 2×2, 3×3, and 4×4 have no tour at all.

How many tours does a chessboard have?

There are 26,534,728,821,064 closed tours if a tour and the same tour run backward count separately. The number of open tours is about 19.6 quadrillion.

Does PictorX upload anything?

No. The board is drawn on a canvas in your browser. Save downloads a PNG, and Edit opens that image in the PictorX editor.