**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