Counting Knight's Tours through the Randomized Warnsdorff Rule

Simple item page
dc.creatorCancela, Héctor
dc.creatorMordecki, Ernesto
dc.date2006-08-31
dc.date.accessioned2026-07-07T07:24:23Z
dc.date.available2026-07-07T07:24:23Z
dc.descriptionWe give an estimate of the number of geometrically distinct open tours $\G$ for a knight on a chessboard. We use a randomization of Warnsdorff rule to implement importance sampling in a backtracking scheme, correcting the observed bias of the original rule, according to the proposed principle that ``most solutions follow Warnsdorff rule most of the time''. After some experiments in order to test this principle, and to calibrate a parameter, interpreted as a distance of a general solution from a Warnsdorff solution, we conjecture that $\G=1.22\times 10^{15}$.
dc.description8 pages. See also http://www.cmat.edu.uy/~mordecki/articles
dc.identifierhttps://arxiv.org/abs/math/0609009
dc.identifierhttp://arxiv.org/abs/math/0609009
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/116329
dc.subjectProbability
dc.subjectCombinatorics
dc.titleCounting Knight's Tours through the Randomized Warnsdorff Rule
dc.typetext

Files

Collections

arXiv