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