home *** CD-ROM | disk | FTP | other *** search
/ AMOS PD CD / amospdcd.iso / 551-575 / apd558 / amoner1 / knight.txt < prev    next >
Text File  |  1993-11-29  |  6KB  |  153 lines
  1.   The "Problem Puzzle" is sort of a competition between our users.
  2. We will bring up a puzzle and ask you to create a program that solves
  3. it. The best program will get published on one of the future Amoner
  4. disks. This disk's puzzle is:
  5.  
  6.                                         The knight's trip
  7.  
  8.  
  9.   The chess board didn't only bring with it a large amount of games
  10. (Chess, Checkers) but also a huge amount of puzzles and problems.
  11. Some of those puzzles are almost impossible to the regular human mind.
  12. Few of them were fully solved only after the computer was created...
  13.  
  14.   The problem we will bring up today does not belong to that group
  15. of problems, as It was solved before the computer was created. Even
  16. so, It's still considered a very elegant problem at the field of
  17. binary trees. When sending us a solution, We will take special
  18. notice of the program's speed when looking for the best program. Yet,
  19. we expect a reasonably good looking display of the solution.
  20.  
  21.  
  22.  
  23.   Ok, now for the problem itself:
  24.  
  25.   One day, when the White King was talking a walk in his royal gardens,
  26. he stumbled across the White knight who sat, with a sad look on his
  27. face, on one of the benches.
  28.  
  29. -  "Hello my loyal Knight" Said the King, "We do look unhappy 
  30. today, don't we?"
  31. - "Oh your highness" the knight bowed, "I been having this little
  32. problem, you see, and I was sitting here all day long trying to solve
  33. it..."
  34. - "What seems to be the problem?" asked the king.
  35. - "Well, I made a bet with the black queen, and the one who loses will
  36. be eaten by the other. I have to solve this little problem by tomorrow
  37. or I'm a horse's meat!"
  38. - "Maybe I can help" suggested the King, "After all, I am well known
  39. for my great wisdom and knowledge!"
  40.  
  41.   The knights eyes lighted with renewed hope. Maybe the king will know
  42. the answer!
  43.  
  44. - "Well, I declared, that by starting from the lower left corner of the
  45. board, I can travel to each of the board's square without stepping
  46. on the same square twice!
  47.  
  48.   The White king scratched his head and said:
  49.  
  50. - "What made you make a damn declaration like that???"
  51.  
  52. - "hmmmm" murmured the Knight, in embarrassment, "You see, she said she
  53. can do it with her queen's movement. I couldn't stand that
  54. show off so I told her I could do it with my knight's movement... Please,
  55. can you help me????"
  56.  
  57. - "No, I can't" said the king pulling an Amiga from under his gown,
  58. "But It can!"
  59.  
  60.   Ok, now, after this "colorful" representation of the problem, let's
  61. take a look at it in a more "dry" mood.
  62.  
  63.   We have a knight standing in the lower left corner of the board 
  64. (Chess's algebraic notation, Square a1.) Using Knight's move, the
  65. knight has to jump to each of the squares in the board, without 
  66. stepping on the same square twice. Another way to look at the problem
  67. is: Can a Knight who stands in the lower left corner visit each one
  68. of the board's squares in 63 moves.
  69.  
  70.   Let's simplify the problem a little. How does a knight move?
  71.  
  72.  
  73.  
  74.   A knight moves two squares in any given
  75. direction and then one square along the 
  76. perpendicular direction. An example of
  77. the possible moves for a knight who stands
  78. in one of the middle squares in shown in
  79. figure 1.
  80.  
  81.  
  82.  
  83.                                        
  84.  
  85.                                     Naturally, a knight cannot leave
  86.                                     the board by moving outside of it.
  87.                                     For example, a knight who stands
  88.                                     in the corner of the board can
  89.                                     move only to two possible squares,
  90.                                     as every other move will lead it
  91.                                     out of the board. (figure 2)
  92.  
  93.  
  94.   If we put the knight on the axis, we can see that if can make
  95. the following moves:
  96.  
  97.                                                         
  98.                                                      X      Y
  99.                                                     ---    ---
  100.  
  101.                                                      1     -2
  102.                                                      2     -1
  103.                                                      2      1
  104.                                                      1      2
  105.                                                     -1      2
  106.                                                     -2      1
  107.                                                     -2     -1 
  108.                                                     -1     -2
  109.  
  110.  
  111.  
  112.   For those of you who like math, it can be quite a simple and cute
  113. math problem to find the equation of the knight moves...
  114.  
  115. Where is exactly the problem?
  116. ----------------------------
  117.  
  118.   Well, You will soon discover that after few moves the knight will
  119. reach a position where it didn't visit all the squares, and getting
  120. to those "unvisited" squares is not possible without visiting a square
  121. on which it already stepped before.
  122.  
  123.   An example of this is shown in figure 4. The blue circles
  124. represent squares which the knight already visited. Some of the
  125. squares are not marked with blue circles. Those are the squares which
  126. the knight still got to visit. But how??? All the squares that
  127. the knight can move into now, were already visited!
  128.  
  129. Solving the Problem.
  130. --------------------
  131.  
  132.   First, let me reassure you that there is a solution to this problem.
  133. I wrote a tiny program using an 8x8 array who calculated every 
  134. possible move of the knight.  However, it took my program a few days(!)
  135. to reach the solution.  Your program must be faster than that.
  136.  
  137.   A friend of mine suggested that a program using 12x12 array will be
  138. faster(!?!?), and I tend to agree but, then again, I'm 
  139. starting to talk too much.  After all, you have to solve the problem,
  140. not me :)
  141.  
  142.  
  143.                                          Good luck.
  144.                                          G. Broner.
  145.                                          Editor. 
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.