Anonymous user
Talk:Knight's tour: Difference between revisions
Incomplete Tours
(Incomplete Tours) |
|||
Line 14:
* [http://www.cmat.edu.uy/~mordecki/articles/warnsdorff.pdf Counting Knight's Tours through the Randomized Warnsdor� Rule, Cancela & Mordecki, 2006] --[[User:Dgamey|Dgamey]] 11:05, 30 May 2011 (UTC)
* [ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/74/442/CS-TR-74-442.pdf Estimating the efficiency of backtrack programs, knuth, 1974] --[[User:Dgamey|Dgamey]] 11:36, 30 May 2011 (UTC)
== Incomplete Tours and Warnsdorff ==
While implementing the Icon/Unicon version over the weekend, I noticed that the algorithm frequently produced incomplete or dead-ended tours. A little investigation proved insightful:
* backtracking unless it can be limited dramatically will be inefficient (Knuth)
* the order the Knight's moves are presented for selection (beyond accessibility) appears to have an effect (Granzfried)
* the algorithm can be probabilistically tuned (Mordecki)
* most papers investigating Warnsdorff indicate that it is imperfect
I haven't measured the hit/miss rate of the Unicon version of the algorithm. There are some aspects that differ from other implementations posted that may be responsible. It would be interesting to compare completion rates of the various implementations. Possible areas of consideration/cause for variance in efficiency:
* using ordered sets to resolve tie breakers. The method (in Unicon) used to generate the 8 possible Knight moves is different and other implementations tend to present them in a given order.
--[[User:Dgamey|Dgamey]] 13:21, 30 May 2011 (UTC)
| |||