Categories
games

The Knight’s Tour

The Knight’s Tour is a sequence of chess moves by a knight on a chessboard such that the piece visits every square only once. How hard could it be?

Animated chess board with a single Knight and no other pieces going to every square on the chess board once

Here’s one possible path that I worked out starting at e1.

e1, g2, h4, f3, e5, g6, h8, f7, d8, b7, a5, c6, d4, b3, a1, c2, b4, a2, c1, d3, c5, a6, b8, d7, f8, h7, g5, e6, f4, h3, g1, e2, g3, h1, f2, e4, c3, d1, b2, a4, b6, a8, c7, b5, a7, c8, d6, e8, f6, g8, e7, d5, e3, c4, a3, b1, d2, f1, h2, g4, h6, f5, g7, h5

The trick is (as far as I can tell) you’ve got to move in a pattern such that at the halfway point your board looks like this:

Chess board with one knight halfway on the Knight's Tour

There might be other ways to complete the tour, but regardless, if you can get sets of two in the block pattern similar to the image above then the rest is just as easy as getting here in the first place. Also, notice that only two corners have been filled at this point. The other general idea is to choose the move that has the least options to move to next (beware there are exceptions).

The knight is randomly placed at the outset but this pattern is buildable from any of the start positions I’ve worked on. Give it a try: The Knight’s Tour. The source code is at github if you’d like to build your own — created by Reddit user psrwo.

(via BoingBoing)