Introduction
This challenge takes place on a chessboard, using only a knight. The knight is only allowed to move in the same way it does in chess - either two squares horizontally and one vertically, or two squares vertically and one horizontally, resulting in an L-shaped move, The X's in the diagram below denote all the current squares to which the knight can travel from the current position. Note that the knight can move over already occupied squares, and that each time the knight moves, it will land on the opposite color square of the one it previously occupied.
The challenge itself is to move the knight, starting at any given square, about the board so that it visits each square only once, and visits EVERY square on the board.
To get an idea of just how challenging this is, try it here (use level 1). Magicians have done it by memorizing whole lists of 64 steps around the board (a good mental feat in and of itself!). Mathematicians have done it by breaking the board down into series of matrix math equations. Computer programmers have found that an efficient way to solve it is to allow the knight to backtrack when he gets trapped.
Is it then possible to solve this puzzle with no backtracking from any square by only relying on your mind? Not only is it possible, but it's surprisingly simple. Magicians are looking for the quickest path to the flashiest show. Mathematicians and computer programmers are trying to break it down into numbers. The method I'll teach requires you understand a few simple patterns that will greatly simplify the problem.
First, I'll teach you a system for solving the puzzle starting from any square on the board. Next, if you desire to continue, I'll show you how to modify this system to allow you to solve this puzzle when someone else chooses both the starting AND ending squares! By the way, you won't often see magicians, mathematicians or computer programmers tackle this latter version of the challenge, as this added restriction makes it much too difficult by their methods. You'll be able to handle it without worry, though.
If you're ready to begin, click here: Learn the knight's tour
Simplifying the problem
To make this problem much simpler, we're going to break down the chessboard into a series of four "quadrants", each consisting of a 4x4 arrangement of squares. Note that each quadrant is exactly identical in terms of the arrangement of black-and-white squares.
Now, working in just a single quadrant, you'll be introduced to four distinct patterns, each of which cover four squares in a quadrant. The first is what I call the "left-hand diamond," due to the fact that it looks like a diamond tilting to the left. The four points of the diamond are points to which the knight can be moved.
The second pattern is called the "right-hand diamond." This diamond, which looks like it's leaning to the right, covers four entirely different squares than the left-hand diamond, but does so in a similar manner - using only legal knight moves.
The third pattern is called the "left-hand square." It is called this because no matter how many 90 degree angles the board is rotated through, the uppermost point will be on the left side of the quadrant. Again, note that the four spaces can be moved to by the knight, and occupy four different chessboard squares than the previous patterns.
The final pattern, not surprisingly, is called the "right-hand square." Like the left-hand square, it is called this because, when rotated, the uppermost point on it will always be on the right side of the quadrant. It covers the final four squares not covered by the previous patterns.
The fact that none of these patterns interferes with squares of the others goes a long way in making the knight's tour MUCH simpler to solve. Once you understand these four basic patterns, click here to continue.
Using the patterns
Having explained the patterns in seperate quadrants of the board, we are now going to bring the entire board back together, in order to employ the patterns. Now, when I refer to diamond or square patterns (left-handed or right handed), that will refer to a pattern in a single quadrant of the board, as explained previously. When I refer to the diamond or square systems, that will refer to the four repeitions of a given pattern over the entire board. For example, here's a completed left-handed diamond system:
You'll note that, from certain points, you can jump from one pattern in a given quadrant to the same pattern in another quadrant. This makes it possible to complete an entire system on the board before moving onto the next system. Due to the fact that each pattern (and thus, each system) uses up squares not employed in the others, this constantly leaves open only legal knight moves!
With these concepts in your mind, I'll now describe the basic way that the knight's tour is solved. After a given square is selected as the starting point:
1. Note which pattern that the knight is in. Is it in a diamond or a square? Right-handed or left-handed?To make this idea even easier to remember, simply remember that you always travel from a diamond system to a square system, and vice versa. Simply complete the system in which you start, and then travel to a system of the opposite shape. Keep doing this until you've filled all 64 squares!
2. Complete all the spaces in that system (for example, if you started in a left-hand diamond pattern, complete all four left-hand diamonds on the board.)
3. Next, jump to any system of the opposite shape. If you just completed an entire square system, start working on either one of the diamond patterns. If you just completed an entire diamond system, start working on either one of the square systems.
4. Once you have two full systems complete - 32 squares on the board (!) - again, start working on a system of the opposite shape. This will be of the same shape you started with, but of the opposite orientation. (For example, if you started in a left-handed diamond, and then completed either one of the square systems, you're now working on a right-handed diamond.)
5. Once you have three systems complete, finish the final pattern - You've completed the Knight's Tour!
It's very important to remember that, when moving from quadrant to quadrant, you work through your pattern in a way that makes sure you can move to the next quadrant.
Here's a video, created by the people at MindMagician.org, that will help you review and understand all you've learned so far:
It sounds amazingly simple, doesn't it? It is. But if you were to try it now, with just the knowledge you have, you'll find that it doesn't always work. You may wonder why you're getting stuck so frequently. To help you solve the basic Knight's Tour without getting trapped, I'll have to teach you about the "Danger Zone" next.
The "Danger Zone"
Below is a diagram of what I term the "Danger Zone", highlighted in red.
In the very center of the board, the knight has 8 possible moves, and other squares allow the knight 6 moves. The squares highlighted as the "Danger Zone" above, allow 4 or fewer possible moves for the knight. Now, as the knight reduces his possible moves each time he moves, anyway, you'll want to keep as many moves open to you as possible.
How do we do this? The simplest way is to remember that each time you complete a system, you want to be as close to the center of the board as is possible. To achieve this, when you begin working on a certain pattern, fill up any squares in the "Danger Zone" as early as possible. Both of the square patterns will have two spaces in the "Danger Zone" (varying depending on the given quadrant). In each quadrant, one of the diamond patterns will only have one space in the "Danger Zone", while the other will have three of it's four spaces in the "Danger Zone!" You can see how easy this makes it to get stuck!
As long as you deal with the "Danger Zone" as early as possible in each pattern, and you practice employing the "Danger Zone" concept, you should be able to solve the Knight's Tour with no backtracking now!
Go ahead and practice your new-found Knight's Tour skills here (use level 1).
Being able to solve the Knight's Tour starting from any space is impressive enough. If you practiced to the point where you're comfortable solving the Knight's Tour as taught here, and you'd like to learn how to let someone choose both the starting AND ending squares, you may continue with the lessons.
Advanced Knight's Tour
You may be worried that letting someone choose a starting square and an ending spaces may make the solution too complicated. Relax! Remember, you probably thought solving the Knight's Tour in ANY manner was complicated before! Assuming you've practiced the basic method taught previously, and you're comfortable with it, you'll only have to learn to make a few adjustments to that method.When letting someone else choose both starting and ending spaces, you must make sure that they are of two opposite colors. If they are the same color, the problem becomes unsolvable, due to the nature of the knight's moves. Don't worry about hiding this fact from anyone for whom you're demonstrating - state it outright!
Surprisingly, once spaces of opposite colors have been specified, there's only three different possible situations you'll have to worry about solving! First, take note of which systems the starting space and the ending space are in. You'll find one of these situations:
1. The starting and ending spaces are in systems of opposite shapes. For example, the starting space is in a diamond system and the ending space is in a square system.You'll solve each of these situations with only minor modifications to the strategies you've learned already. Remember these modifications and when to use them, and you'll be able to handle ANY Knight's Tour challenge:
2. The starting and ending spaces are in systems of the same shape, but opposite orientations. For example, the starting space is in a left-hand diamond, and the ending space is in a right-hand diamond.
3. The starting and ending spaces are systems of the same shape and orientation. For example, the starting and ending spaces are both in right-handed squares.
Situation 1: Starting and Ending Spaces are in Systems of Opposite Shapes
This one is simple. Just as you've learned previously, you'll complete one system, then skip to a system of the opposite shape. Make sure, though, that the second system you enter DOES NOT contain the ending space. After you complete three full systems, make sure to enter the final system in such a way that your last move is the designated ending space. With practice, this isn't difficult.Summary: Diamond / square / 2nd diamond / 2nd square - OR - square / diamond / 2nd square / 2nd diamond (Just make sure to choose your systems with respect to the location of the ending space)
Situation 2: Starting and Ending Spaces are in Systems of the Same Shapes, and Different Orientations
This one is a little trickier. Complete the first system, then move to a system of the opposite shape and complete that one, just as you originally learned. The third system you enter, though, will contain the ending space. When you enter this third system, take care of just a few spaces in one pattern (preferably "Danger Zone" spaces) that are not the ending square, and then move into an opposite system and complete it. After that, go back to the remaining system and complete it. Again, practice will help you solve any minor problems you encounter doing this.Summary: Diamond / square / partial 2nd diamond / 2nd square / remainder of 2nd diamond - OR - square / diamond / partial 2nd square / 2nd diamond / remainder of 2nd square
Situation 3: Starting and Ending Spaces are in Systems of the Same Shapes and Orientations
This one employs the shape-portioning idea from Situation 2 (above). In this case, you complete only a few squares of the initial system. Finally, go back and complete the initial system.Summary: Partial 1st diamond / 1st square / 2nd diamond / 2nd square / remainder of 1st diamond - OR - partial 1st square / 1st diamond / 2nd square / 2nd diamond / remainder of 1st square
To review and better understand the advanced Knight's Tour, check out this video from the people at MindMagician.org:
Posts
No Response to "Knight's Tour"
Post a Comment