From: Daniel Martin <martin@...>
Date: 2006-08-17T02:39:12+09:00
Subject: Re: [QUIZ] Some observations on Pen and Paper (#90) or to make it fast, choose your algorithm wisely

"Rick DeNatale" <rick.denatale@gmail.com> writes:

> However, sometime after the advent of computers, it was shown that
> Warnsdorff's approach runs into blind alleys for boards bigger than
> 76x76.
> http://mathworld.wolfram.com/KnightsTour.html

Yeah, I ran across that while working on an algorithm.  Empirical
results here would suggest that this isn't the case for this
particular set of move conditions.

> I'm not sure if anyone has gotten into the 20th century.  In 1992,
> Conrad, et al. found an algorithm which subdivides the board into
> smaller pieces of 8x8 or less, finds a path for each sub-piece which
> links from one sub-piece to another in an order which covers the
> board. Because solving the small boards is very quick, this
> divide-and-conquer approach works really well.

One of the approaches used (Elliot Temple's second solution) took this
5-by-5 solution:

17,  9,  2, 18, 24
 4, 14, 22,  7, 13
 1, 19, 25, 10, 20
16,  8,  3, 15, 23
 5, 11, 21,  6, 12

And then replicated it over and over to cover the board.  Note that
this solution begins in the middle of a side and ends in the center -
this means that you can jump from the end of one subsolution to the
beginning of the next, and can therefore cover the entire board in an
S pattern like this:

--------------------\
                    |
/-------------------/
|
\-------------------\
                    |
/-------------------/

Of course, this only works for boards whose sizes are a multiple of
five, a major disadvantage.  To handle boards of arbitrary size, you'd
probably have to give up on using a canned 5-by-5 solution or at the
very least you'd need to have composeable solutions for 5-by-X, for X
in (5..9) as well as a solution for X-by-Y for X and Y in (5..9).
(But that last solution could end anywhere, since you wouldn't need to
jump away from it)

Note that for boards whose sides are a multiple of 10, you could use a
different pattern for where the subboards went, and as a result even
get a circular solution: 

/---------\
| /-\ /-\ |
| | | | | |
| | | | | |
| | | | | |
\-/ \-/ \-/