🚀 go-pugleaf

Androcles wrote:
[snip]
> Okay, well, for amusement only:
> There is a well-known little puzzle known as the "Knight's Tour".
> The object of the puzzle is to have the (chess) knight visit all 64 squares
> on the chessboard
> once and once only, according to his usual move, being 1 square in x, two
> squares in y, or 1 square in y and two in x.
> First question:
> After the knight has completed the tour, what is the least number of moves
> needed to return to the starting position?
> Second question:
> Can this result be modified by taking a different tour?
[snip]

I am not sure I understand the first question (least number of moves),
but the Knight's tour puzzle has a known solution. You can find an
optimal tour by selecting always your next move according to the rule:
The available moves from your next move's spot has to be minimal. So, to
elaborate: If the Knight can move into positions x1, x2,..x8 (in
general), and denote by nm(xn) the number of available moves at place
xn, then a valid next move (that leads to a solution) would be xi, where
nm(xi)=min{nm(xj),j=1..8}.

An interesting side effect to a solution followed by the above
algorithm, is that if you number the squares according to the order
visited, you get a magic square. Since the chessboard is 8x8, this would
be a non-trivial magic square, contrary to odd sided squares which can
get formed by laying the natural numbers in diagonals.
Cheerio

> Androcles

-- 
Ioannis Galidakis jgal@ath.forthnet.gr
<http://www.crosswinds.net/athens/~jgal/main.html>
______________________________________
"Blessed are the ones who can laugh at themselves,
for they shall never cease to be amused."