The "Problem Puzzle" is sort of a competition between our users. We will bring up a puzzle and ask you to create a program that solves it. The best program will get published on one of the future Amoner disks. This disk's puzzle is: The knight's trip The chess board didn't only bring with it a large amount of games (Chess, Checkers) but also a huge amount of puzzles and problems. Some of those puzzles are almost impossible to the regular human mind. Few of them were fully solved only after the computer was created... The problem we will bring up today does not belong to that group of problems, as It was solved before the computer was created. Even so, It's still considered a very elegant problem at the field of binary trees. When sending us a solution, We will take special notice of the program's speed when looking for the best program. Yet, we expect a reasonably good looking display of the solution. Ok, now for the problem itself: One day, when the White King was talking a walk in his royal gardens, he stumbled across the White knight who sat, with a sad look on his face, on one of the benches. - "Hello my loyal Knight" Said the King, "We do look unhappy today, don't we?" - "Oh your highness" the knight bowed, "I been having this little problem, you see, and I was sitting here all day long trying to solve it..." - "What seems to be the problem?" asked the king. - "Well, I made a bet with the black queen, and the one who loses will be eaten by the other. I have to solve this little problem by tomorrow or I'm a horse's meat!" - "Maybe I can help" suggested the King, "After all, I am well known for my great wisdom and knowledge!" The knights eyes lighted with renewed hope. Maybe the king will know the answer! - "Well, I declared, that by starting from the lower left corner of the board, I can travel to each of the board's square without stepping on the same square twice! The White king scratched his head and said: - "What made you make a damn declaration like that???" - "hmmmm" murmured the Knight, in embarrassment, "You see, she said she can do it with her queen's movement. I couldn't stand that show off so I told her I could do it with my knight's movement... Please, can you help me????" - "No, I can't" said the king pulling an Amiga from under his gown, "But It can!" Ok, now, after this "colorful" representation of the problem, let's take a look at it in a more "dry" mood. We have a knight standing in the lower left corner of the board (Chess's algebraic notation, Square a1.) Using Knight's move, the knight has to jump to each of the squares in the board, without stepping on the same square twice. Another way to look at the problem is: Can a Knight who stands in the lower left corner visit each one of the board's squares in 63 moves. Let's simplify the problem a little. How does a knight move? A knight moves two squares in any given direction and then one square along the perpendicular direction. An example of the possible moves for a knight who stands in one of the middle squares in shown in figure 1. Naturally, a knight cannot leave the board by moving outside of it. For example, a knight who stands in the corner of the board can move only to two possible squares, as every other move will lead it out of the board. (figure 2) If we put the knight on the axis, we can see that if can make the following moves: X Y --- --- 1 -2 2 -1 2 1 1 2 -1 2 -2 1 -2 -1 -1 -2 For those of you who like math, it can be quite a simple and cute math problem to find the equation of the knight moves... Where is exactly the problem? ---------------------------- Well, You will soon discover that after few moves the knight will reach a position where it didn't visit all the squares, and getting to those "unvisited" squares is not possible without visiting a square on which it already stepped before. An example of this is shown in figure 4. The blue circles represent squares which the knight already visited. Some of the squares are not marked with blue circles. Those are the squares which the knight still got to visit. But how??? All the squares that the knight can move into now, were already visited! Solving the Problem. -------------------- First, let me reassure you that there is a solution to this problem. I wrote a tiny program using an 8x8 array who calculated every possible move of the knight. However, it took my program a few days(!) to reach the solution. Your program must be faster than that. A friend of mine suggested that a program using 12x12 array will be faster(!?!?), and I tend to agree but, then again, I'm starting to talk too much. After all, you have to solve the problem, not me :) Good luck. G. Broner. Editor.