From: Rick DeNatale <rick.denatale@...>
Date: 2006-08-17T01:46:52+09:00
Subject: [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
http://www.axel-conrad.de/springer/springer.html

This page is in German.  The google translation is somewhat readable,
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
http://talklikeaduck.denhaven2.com/