What is the longest possible closed path of a chess king on the chessboard that does not cross itself?

competition/games/chess/king.longest.tour New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

What is the longest possible closed path of a chess king on the
chessboard that does not cross itself?  (The king visits every square;
a step between squares of the same colour is sqrt(2) long, a step
between squares of different colours is 1 long.)

[ Editor: problem statement reconstructed from the solution posting,
titled "CHESS KING - SUPER-STAR". ]

Show solution

The problem was to find the longest possible closed way on the
chessboard, that does not cross itself.

1. The trajectory contains 64 steps exactly.
2. The step between fields of the same colour is sqrt(2) long, and
   between fields of the different colours is of unit length.
3. The king has to change the colour of the field the least possible
   times.

4. Consider the bordering fields, i.e. A1,..A8,B8,..H8,H7,..H1,G1..B1.
   The King can not cross not only his trajectory, but the border of
   the board itself, so the the part of his trajectory between two
   border fields divides the board onto two parts, and the King can not
   move from the interor of one part into the interior of another one.
5. This means, that the King comes to the border fields in a sequential
   order. I.e. (as there are two directions, let us assume, that he
   went from A1, and wisited A3 after A2) he reaches A4 only after A3
   and before A5.
6. The fields in this sequence has changing colour, and as there are
   30 border fields, he has to change colour 30 times, so there are not
   less than 30 steps of unite length, and, hence, no more than 34
   diagonal ones of sqrt(2) length.

[ Editor: the border listed in step 4 has 4*8 - 4 = 28 fields, not
30. ]

7. The longest way can not exceed 30+34sqrt(2).
8. The example of the trajectory of 30+34sqrt(2) length is rather easy.

-- Pertsel Vladimir <voldemar@wiscon.weizmann.ac.il>

[ Editor: no example trajectory was given in the collected posting. ]