Knight 39;s Tour Puzzle

[Marcelo Chaplin]

This is a puzzle I made years ago for a Scottish Correspondence Chess Magazine - it is a knight's tour (where knight has to touch each square once only and then on to the next with legal knight moves) but it also spells a message. The clues I will give: start at what would be d1 on a chessboard (THE LETTER IS A), it forms a question and the word structure is (3/3/4/7/5/5/7/2/2/2/10/6/8). It is so long since I devised it I had to work it out from scratch again myself; why did I never think to save the answers to these things...?

Knight's tours are a hobby of mine and my literacy skills are excellent, so between the two of them the pattern recognition wasn't too hard. But I'd have used a different tour based on a method I evolved some years back, so it didn't give me that much of an advantage. Fun puzzle, thanks very much.

or their reflections. After executing one of these, begin another such pattern in an adjacent quadrant, starting carefully so as to leave the Knight an exit at the end of the pattern. With a little practice you can start stringing these patterns together to create complete tours, and after that, the world's your oyster.

Gil-Gandel that is really awesome. I had always wanted to see one. First time I heard of knight tours I think was in the novel The Eight by Katherine Neville and she mentioned mathematical closed tours....it led on to my developing my relatively dumbed down one but always wondering. My eyes are opened.

Thats pretty impressive. I feel totally amateur now. Not that I didnt know that way better minds than mine had worked on the tours. Most of all, though, I am delighted that you guys have posted this stuff - it means I can always access it from my home page. Thanks, guys.

Another pattern that I used to try resulting in a quasi-symmetrical tour: As stated, a Knight can't tour on a 4x4 board, but it can if you cut off two opposite-coloured corners. So consider the centre of the board - c-file to f-file, 3rd rank to 6th. Leave out c3 and f3. The idea is to begin somewhere in the outer ring which comprises 50 squares, and visit 25 of them, so that the 25 squares you have visited and the 25 you haven't are mirror images. The 26th square you visit should be d3 or e3 depending what colour square you started on. You then tour the 14-square inner zone, leaving e3 or d3 (whichever one you didn't enter by) until last. It then follows that your last 25 moves will be mirror images of the first 25.

1) Define a board as an 8x8 array. For each square store two values: Accessibility, meaning the number of squares that are a Knight's move away (2 for a corner square, 8 for a centre, somewhere in between for others) and Remoteness, the distance of the square from the centre (the number of 1-square orthogonal moves you would have to make to reach d4, d5, e4 or e5, whichever's nearest). Starting at any square, you repeatedly do the following:

A chess knight can travel around a chessboard using the knight's move and visit every square once, and only once. This is known as the Knight's Tour. The Knight's Tour is usually played with numbered counters on a conventional chessboard (Figure 1), but you can play it on any rectangular board with five or more rows and columns.

The Knight's Tour is an example of a classic mathematical problem that lends itself to easy and creative expression through computer programming. I created a Python program to help users practice solving the Knight's Tour. The Knight's Tour program is a good example of the simple yet powerful applications you can build with the Pygame Python library for computer gamers.

At first, solving the Knight's Tour seems to be a daunting challenge, but quite a few strategies exist that will help you solve the puzzle [1]. I'll consider just two of them. The first strategy is usually known as the Diamonds and Squares method, and it's a simple party trick that anyone can learn in minutes.

Solving the Knight's Tour using the Diamonds and Squares technique doesn't require any mathematical talent or much logical skill; it merely requires the player to recognize two simple geometric shapes in the patterns of knight's moves. This approach can produce a relatively small number of apparently unique tours from every starting square, but the symmetry of the chessboard means that many of these solutions are transformations of other tours by rotation, reflection, or inversion, and this simple technique can only produce 46 truly unique Knight's Tours on a chessboard. Most of the Knight's Tour solution videos you watch on YouTube and elsewhere demonstrate the Diamonds and Squares method.

The second approach is known as Warnsdorff's rule. This strategy takes a bit more effort to master. On an 8x8 chessboard, it can produce thousands of different Knight's Tours from any starting square, but, again, the symmetry of the chessboard means that not all of these solutions are truly unique and many of them are transformations of other Warnsdorff's rule tours. As you'll see in a moment, Warnsdorff's rule can sometimes lead to an impasse, but it still produces far more solutions than the Diamonds and Squares method.

If you want to impress your friends by showing them how to solve the Knight's Tour, then using Warnsdorff's rule will not expose you as a chess puzzle pretender, but using the simple Diamonds and Squares technique might put your reputation as a chess puzzle genius in jeopardy.

The Diamonds and Squares technique was first described by C. R. R. von Schinnern in 1826 [1]. It only works on boards that have at least 8x8 squares. Larger boards must have a number of rows and columns that are a multiple of four (i.e., 12x12, 8x16, and so on). Unlike Warnsdorff's rule, the Diamonds and Squares technique cannot be used to solve the Knight's Tour on a 6x6 or a 10x10 board.

To employ the Diamonds and Squares strategy on a conventional 8x8 chessboard, you need to divide the chessboard into four quadrants and understand how four knights can be placed on a quadrant in four distinct patterns. The first of these patterns is described as a right-hand (RH) diamond (Figure 2a). The second is a left-hand (LH) diamond (Figure 2b), the third is a RH square (Figure 2c), and the last one is a LH square (Figure 2d). When these four shapes are joined together on one quadrant of the chessboard, all 16 squares in that quadrant will have a knight on them.

In order to use the diamond and square shapes to solve the Knight's Tour, you need to know whether the first knight placed on the board is on a diamond (either RH or LH) or on a square (either RH or LH). For example, a knight at b3 is on a RH diamond (Figure 3a), one at c4 is on a RH square (Figure 3b), a knight at d1 is on a LH diamond (Figure 3c), and one at d3 is on a LH square (Figure 3d).

If you place the first knight on, for example, b3, then you can complete a four-knight partial tour in the lower left-hand quadrant with four knights on a RH diamond shape (Figure 3a). You then move onto an adjacent quadrant and use a RH diamond shape to complete another four-knight partial tour on that quadrant. Then you can move on to a third quadrant and then the fourth so that all four quadrants have a four-knight, RH diamond-shaped partial tour on them, and there are 16 knights on the board (Figure 3a). After completing the RH diamond-shaped partial tour, you move on to a square-shaped partial tour, in this example, a RH square-shaped partial tour starting at c4 and ending at d6 (Figure 3b). Then you can complete a LH diamond-shaped partial tour starting at e8 and ending at b6 (Figure 3c) and finally a LH square-shaped partial tour starting at d7 and ending at g5 to complete the Knight's Tour (Figure 3d).

The Knight's Tour can always be solved by combining two, 16-knight, diamond-shaped, LH and RH partial tours and two, 16-knight, square-shaped, LH and RH partial tours in the order diamond-square-diamond-square or square-diamond-square-diamond. You will need to make sure that the fourth knight placed in each quadrant leads to an empty square on an adjacent quadrant. With a bit of practice, it's quite easy to solve the Knight's Tour from any starting square using this method.

You can find variations of the Diamonds and Squares technique that will allow you to choose the starting and ending square, but be warned, nearly everyone who knows about the Knight's Tour knows about the Diamonds and Squares method, and you can only impress naive chess puzzlers by demonstrating this technique.

The second strategy is known as Warnsdorff's rule [1, 2] and it is named after H. C. von Warnsdorff, who first described it in 1823. Warnsdorff's rule is a heuristic or rule-of-thumb method for finding a Knight's Tour from any starting square on any sized board with at least 5x5 squares. I'll look at it on a conventional chessboard.

1. With each move, you have to look ahead to see which of the possible next moves has the least number of exits that can be taken using the knight's move (Figure 4). An exit is a legal move to a square that the knight hasn't inhabited yet.

Unfortunately, if a Monte Carlo test [3] is done when Warnsdorff's rule is applied to a conventional chessboard, about three percent of the attempts to find a complete tour will lead to an impasse. If you want to find a Knight's Tour every time using Warnsdorff's rule, you need to modify the original rule to overcome any impasse that might occur. Do this by replacing the random choice of a tiebreaker with a systematic choice.

Another variant of Warnsdorff's rule is better if you're trying to find a way out of an impasse by hand, because it usually involves less work than starting again. If systematic tie breaking leads to an impasse, you can backtrack to the last tiebreaker and take the second-priority move. If that doesn't work, you can backtrack again and choose the third-priority move, and so on until all the tiebreakers have been tried. If that doesn't overcome the impasse, backtrack to the last-but-one tiebreaker, select the second priority tiebreaker, and keep doing this until the impasse is overcome. The computer program will enable you to backtrack in this way if you're using Warnsdorff's rule (or any other strategy) to solve the puzzle by hand and you get stuck in an impasse. The program doesn't use backtracking when it's finding a solution for you, but if you'd like to see how a program can use backtracking to find a way out of an impasse, there's a backtracking algorithm used in a Knight's Tour program I wrote when I first became interested in chess puzzles many years ago. This program was published in The Century/Acorn User Book of Computer Puzzles [4].

c80f0f1006