Knights Tour : Proof of Correctness

Article View: comp.theory

Article #2005

#2005

From: Ajay Shekhawat
Date: Wed, 10 Jan 1990 01:22

19 lines
1365 bytes

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

Technical Details

Message-ID: <15636@eerie.acsu.Buffalo.EDU>

Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!rutgers!sunybcs!sybil.cs.Buffalo.EDU!ajay

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!rutgers!sunybcs!sybil.cs.Buffalo.EDU!ajay
From: ajay@sybil.cs.Buffalo.EDU (Ajay Shekhawat)
Newsgroups: comp.theory,rec.puzzles
Subject: Knights Tour : Proof of Correctness
Message-ID: <15636@eerie.acsu.Buffalo.EDU>
Date: 10 Jan 90 01:22:17 GMT
Sender: nobody@acsu.Buffalo.EDU
Reply-To: ajay@cs.Buffalo.EDU ( Ajay Shekhawat )
Followup-To: comp.theory
Organization: University at Buffalo, Dept. of Computer Science
Lines: 19