Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Ruby (http://www.velocityreviews.com/forums/f66-ruby.html)
-   -   [QUIZ] Some observations on Pen and Paper (#90) or to make it fast, choose your algorithm wisely (http://www.velocityreviews.com/forums/t832503-quiz-some-observations-on-pen-and-paper-90-or-to-make-it-fast-choose-your-algorithm-wisely.html)

 Rick DeNatale 08-16-2006 04:46 PM

[QUIZ] Some observations on Pen and Paper (#90) or to make it fast, choose your algorithm wisely

Looking at the solutions posted so far, it seems:

1) Those who have done best have recognized the relation between this
problem and the well-known Knight's Tour problem first posed by
Leonhard Euler in 1758.

2) Some, like me, solved the problem with a straightforward
backtracking approach. This approach is well known to get slow quickly
with increasing board sizes. At least this approach provably will
find a solution if it exists, or announce correctly that it doesn't.
So this is a point for us 18th century types.

3) The fast ones seem to be based on Warnsdorff's algorithm for the
Knight's tour which was published in 1823. So those guys are at least
in the 19th century.

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

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.

I don't think that anyone has attempted to solve the quiz using
Conrad's approach. The complications seem to be correctly carving up
the board, stringing the sub-boards together in some sequence, and
finding paths which allow movement from one sub-board to another in
that sequence.

I thought I saw someone say that his solution sub-divided the board
up, but I can't seem to find it now.

The key observation is that the key to making a program fast is to
find the right algorithm.

P.S. Axel Conrad's page on the 1992 algorithm is at

and enhances the humor on Conrad's informal report on the algorithm.

'It was invented long ago, more than 200 years ago, more exactly in
the year 1758, by a Swiss. This Swiss was not smaller than Leonhard an
Euler, who sat in Berlin and a beautiful evening to these like today
too does not tiefst at that time provinzielle city thought, but to
something larger, to a chessboard: "An empty chessboard is given. Is
there a Zugfolge, with that Springer all (black and white) fields of
the board exactly once been visiting?"'

I'm guessing that "not smaller than" really should be "no less than".
I know that a Springer is the German word for a chess knight, and I
guess Zugfolge is something like "path."

Then after introducing the notion of solving the problem for boards
bigger than the standard 8x8 chess board:

'As said, Euler was Swiss, and Swiss are considered generally as very
conscientious and just as slow. Perhaps this applies also to the
solution of Swiss problems, anyhow could the Springer problem in the
next 200 years not be solved.'

--
Rick DeNatale

My blog on Ruby

 Justin Collins 08-16-2006 05:07 PM

Re: [QUIZ] Some observations on Pen and Paper (#90) or to make itfast, choose your algorithm wisely

Rick DeNatale wrote:
<snip>
> 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.
>
> I don't think that anyone has attempted to solve the quiz using
> Conrad's approach. The complications seem to be correctly carving up
> the board, stringing the sub-boards together in some sequence, and
> finding paths which allow movement from one sub-board to another in
> that sequence.
>
> I thought I saw someone say that his solution sub-divided the board
> up, but I can't seem to find it now.
>

<snip>

It's right here:

Elliot's solution uses 5x5 'pre-solved' solutions to fill the board.

-Justin

 Daniel Martin 08-16-2006 05:39 PM

Re: [QUIZ] Some observations on Pen and Paper (#90) or to make itfast, 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:

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

 All times are GMT. The time now is 11:36 PM.