[rec.puzzles] Knights Tour : Proof of Correctness

ajay@sybil.cs.Buffalo.EDU (Ajay Shekhawat) (01/10/90)

Hi,
	I'm   looking  for    a  proof   of   correctness  for     the
(non-backtracking) Algorithm  to solve the   Knights Tour Problem. The
algorithm is based on the following  rule:  "The knight must always be
moved to one of  the squares from which there  are the fewest exits to
squares not already visited." According to Horowitz &  Sahni [1], this
rule was given by J.C. Warnsdorff in 1823. Any references to the proof
of correctness would be greatly appreciated.

Thanks in Advance,
			Ajay..
     

[1] Horowitz,  E.,  & Sahni,  S.,  "Fundamentals of  Data Structures",
    1983, Comp. Sc. Press, pp. 74.

-------------------------------------------------------------------------------
Ajay Shekhawat           < Deptt. of CS , SUNY @ Buffalo , Buffalo , NY 14260 >
ajay@cs.Buffalo.EDU || ajay@sunybcs.BITNET || ajay@sunybcs.UUCP || 716-636-3027