[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

494.0. "Re-entrant Knight's Tours (i.e., a cycle)" by CLT::GILBERT (Juggler of Noterdom) Sat May 31 1986 00:28

Newsgroups: net.math
Path: decwrl!pyramid!pesnta!hplabs!qantel!lll-lcc!lll-crg!seismo!mcvax!ukc!warwick!ds
Subject: looking for knight's tour information
Posted: 25 May 86 15:03:14 GMT
Organization: Maths institute, University of Warwick, UK
 
Xpath: ukc eagle
 
I have recently been tinkering with re-entrant knight's tours on rectangular
boards of various sizes, and have found examples or proofs of impossibility
on all board sizes except (4a+2) by (4b+1).
 
If anyone knows whether tours on such boards exist, could they send me one?
If not, does anyone have a proof of non-existence ?
 
I am interested now only in sizes like 6x5, 6x9, 10x5 or 10x9.
Please MAIL me, don't post, and I will summarize to the net.
 
[ A re-entrant knight's tour is a sequence of knight's moves on a chessboard
such that each square is visited once exactly, and the tour finishes back
where it started ]
 
Apologies if this topic has already been 'done to death'.
--
+---------------------------------+-------------------------+
| 'Anchoring on his left foot and | Douglas Spencer         |
| balancing poised over the talc- |  Mathematics Institute  |
| like  pulverate,  testingly  he |   University of Warwick |
| put his right foot in.'         |    Coventry             |
| Who is it? What story is this?  |     CV4 7AL             |
| What happens next? Please email |      England            |
+---------------------------------+-------------------------+
|  ..seismo!mcvax!ukc!warwick!ds  | 1,29'35" W  52,25'15" N |
+---------------------------------+-------------------------+
T.RTitleUserPersonal
Name
DateLines
494.1Hard to draw pictures on these terminalsMODEL::YARBROUGHMon Jun 02 1986 16:244
    I have found 5x6 and 5x10 tours, but they hard to draw here. Any
    suggestions as to how to represent them?
    
    Lynn Yarbrough
494.2Here are some solutionsMODEL::YARBROUGHMon Jun 02 1986 17:4124
    5x6:
    01 18 07 22 03 16
    08 27 02 17 12 23
    19 30 21 06 15 04
    26 09 28 13 24 11
    29 20 25 10 05 14
    
    5x10:
    01 20 15 34 03 22 05 36 43 24
    32 13 02 21 16 35 42 23 06 37
    19 50 33 14 29 04 39 08 25 44
    12 31 48 17 10 41 46 27 38 07
    49 18 11 30 47 28 09 40 45 26
    
    6x9:
    01 26 37 34 03 18 49 14 05
    38 33 02 27 36 15 04 19 48
    25 54 35 42 29 50 17 06 13
    32 39 28 51 16 43 10 47 20
    53 24 41 30 09 22 45 12 07
    40 31 52 23 44 11 08 21 46
    
    I'll leave the 9x10 case as an exercise for the reader :-)
    
494.3A nice programming problemZFC::DERAMOFrustrated personal name composerMon Dec 21 1987 22:5432
    I remember reading a long time ago that a good technique for finding
    Knight's tours [on square boards of even length] was to take the
    next step based on this rule:
    
         move to an open square from which you can move to an
         open square which minimizes the number of next moves
         available
    
    [By open I mean a square not yet reached on the tour.]
    
    So if you have possible moves x1, x2, x3 and from these you
    have
           x1 -> x11 and now there are 2 possible moves
           x1 -> x12 and now there are 3 possible moves
    
           x2 -> x21 and now there are 2 possible moves
           x2 -> x22 and now there is  1 possible move
           x2 -> x23 and now there are 4 possible moves
    
           x3 -> x31 and now there are 2 possible moves
           x3 -> x32 and now there are 2 possible moves
    
    then the rule says to take move x2.  You will not necessarily
    then take move x22; you have to reapply the rule to the board
    as it is after move x2.
    
    I programmed this long ago and it worked fine for the cases I 
    tried.  I can only recall trying even square or even by even
    rectangular boards.  There is no guarantee that the solution
    generated can go from the last square to the first.
    
    Dan