What is the smallest number of moves in which a bishop, starting where he chooses, can visit (pass into or...

neill@macro.demon.co.uk (Neill Clift) writes:

>I coded up a program to search for this solution and sure enough it
>was looking like this was the best I was going to do.  In order to get
>the program to run fast enough I had made some initial prunes that
>were obviously not strictly correct (each move must capture at least
>one square).  Talking to a colleague at work about what possible
>prunes I could use so that I could cover the full space quickly he
>attempted to find a shorter tour on paper.  He quickly found a tour of
>length 16 that had the property that it did have a move that captured
>zero squares (it started a1 h8 so move two captured no squares).
>David Wells' book didn't seem to say anything that prevents a solution
>like this.  Maybe he just transcribed the problem incorrectly from his
>reference (Domoryad, A. P. (1963) Mathematical Games and Pastimes).
>Anyone have this book and can check?

Wells' book shortens the statements of puzzles quite a bit and has been
known to be erroneous.  (I believe the rec.puzzles archive actually
cites one mistake in that book.)  I don't have Domoryad's reference,
but no doubt one of the earliest appearances of this puzzle was by
H. E. Dudeney, the 19th century British "puzzle king."  The problem
appears in the collection "536 Puzzles and Curious Problems" as number
422, "The Fly's Tour":

  A fly pitched on the square in the top left-hand corner of a
  chessboard, and then proceeded to visit every white square.  He did
  this without ever entering a black square or ever passing through
  the same intersection (where a horizontal and vertical line meet)
  more than once.  Can you show his route?  It can be done in seventeen
  continuous straight courses.

The question is obviously phrased to leave only the beautiful 17-move
answer.

Relaxing the restrictions will still leave a minimum of 16 moves:

No edge or corner square can be passed through, i.e., every move using
that square must stop there.  This means, given one such square, it is
either an endpoint of the tour and hence the endpoint of 1 move, or the
endpoint of 2 moves.  This accounts for at least 26 endpoints of moves.
The "loops" a3-c1-h6-f8, a5-e1-h4-d8, a7-g1-h2-b8, and a1-h8 cannot be
escaped without adding more move-endpoints.  This adds at least 6 more
move-endpoints, as two loops must be exited and entered.  This brings
the number of necessary move endpoints up to 32.  Since each move has
two endpoints, the minimum number of moves needed is at least 16.

-- Wei-Hwa Huang <whuang@ugcs.caltech.edu>

[ Editor: Wells's book uses a black-squared bishop in his 17-move
  solution although the question says white (Clift); the 17-move
  solution itself was not reproduced in the posting.  The archive's
  references/books/bloopers lists Wells's book (#373 and #554) under
  probability/apriori. ]