[Search for users]
[Overall Top Noters]
[List of all Conferences]
[Download this site]
| 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) Fri May 30 1986 21: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.R | Title | User | Personal
Name | Date | Lines |
|---|
| 494.1 | Hard to draw pictures on these terminals | MODEL::YARBROUGH | | Mon Jun 02 1986 13:24 | 4 |
| I have found 5x6 and 5x10 tours, but they hard to draw here. Any
suggestions as to how to represent them?
Lynn Yarbrough
|
| 494.2 | Here are some solutions | MODEL::YARBROUGH | | Mon Jun 02 1986 14:41 | 24 |
| 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.3 | A nice programming problem | ZFC::DERAMO | Frustrated personal name composer | Mon Dec 21 1987 19:54 | 32 |
| 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
|