home *** CD-ROM | disk | FTP | other *** search
/ Oakland CPM Archive / oakcpm.iso / sigm / vol245 / tour.lbr / 4X.HLP < prev    next >
Encoding:
Text File  |  1986-02-11  |  2.5 KB  |  77 lines
  1. introduction
  2. 4X3.TOU
  3. 4X3.ASM
  4. 4X3.COM
  5. 4X5.TOU
  6. 4X5.ASM
  7. 4X5.COM
  8. 4X6.TOU
  9. 4X6.ASM
  10. 4X6.COM
  11. 4X7.TOU
  12. 4X7.ASM
  13. 4X7.COM
  14. 4X8.TOU
  15. 4X8.ASM - won't fit
  16. 4X8.COM
  17. 4GRID
  18. :Introduction.
  19.  
  20.     We have a collection of knight's tours for a 4xN strip, with N running
  21. between 3 and 8. According to Kraitchik, the key to understanding the 4xN strip
  22. is to group the squares into four classes - outer red, outer black, inner red,
  23. and inner black. A knight ALWAYS alternates between red and black squares. For
  24. the 4xN strip, marked as shown,
  25.  
  26.           +-------+-------+-------+-------+-------+-------+-------+-------+
  27.           |   A   |   B   |   A   |   B   |   A   |   B   |   A   |   B   |
  28.           +-------+-------+-------+-------+-------+-------+-------+-------+
  29.           |   a   |   b   |   a   |   b   |   a   |   b   |   a   |   b   |
  30.           +-------+-------+-------+-------+-------+-------+-------+-------+
  31.           |   b   |   a   |   b   |   a   |   b   |   a   |   b   |   a   |
  32.           +-------+-------+-------+-------+-------+-------+-------+-------+
  33.           |   B   |   A   |   B   |   A   |   B   |   A   |   B   |   A   |
  34.           +-------+-------+-------+-------+-------+-------+-------+-------+
  35.  
  36. a more specialized transition diagram holds:
  37.  
  38.                 A <---> a <---> b <---> B
  39.  
  40. -
  41. The rule is that ALL the A's must be visited before ANY B's (or conversely).
  42. Moreover, only A's and B's can be terminal points, otherwise the gap between
  43. a's and b's could never be bridged.
  44.  
  45. Since there are equal numbers of A's, a's, B's and b's, any premature jumps
  46. between a's and b's will use up one of the a's that has to be paired with
  47. an A.
  48.  
  49.     Kraitchik also reports a symmetry, beyond the obvious rotational
  50. and reflective symmetry of a rectangle - small and capital letters may be
  51. interchanged. That is, the top two rows may be exchanged, simultaneously
  52. the bottom two rows, and you will get another tour.
  53.  
  54.     The number of tours for various cases should be:
  55.  
  56.     N =        3    4    5    6    7    8
  57.     tours =        8    0      82     744    6378   31088
  58.  
  59. :: (TOUR)4X3.TOU
  60. :: (TOUR)4X3.AQM
  61. :: P=(TOUR)4X3.COM (TOUR)NULL.HLP
  62. :: (TOUR)4X5.TOU
  63. :: (TOUR)4X5.AQM
  64. :: P=(TOUR)4X5.COM (TOUR)NULL.HLP
  65. :: (TOUR)4X6.TOU
  66. :: (TOUR)4X6.AQM
  67. :: P=(TOUR)4X6.COM (TOUR)NULL.HLP
  68. :: (TOUR)4X7.TOU
  69. :: (TOUR)4X7.AQM
  70. :: P=(TOUR)4X7.COM (TOUR)NULL.HLP
  71. :: (TOUR)4X8.TOU
  72. : (TOUR)4X8.AQM - too big to fit in memory
  73. :: P=(TOUR)4X8.COM (TOUR)NULL.HLP
  74. :: (TOUR)4GRID.HQP
  75. :[end]
  76. [Harold V. McIntosh, 15 July 1985]
  77.