Counting Knight's Tours through the Randomized Warnsdorff Rule

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We 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}$.
8 pages. See also http://www.cmat.edu.uy/~mordecki/articles

Keywords

Probability, Combinatorics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/116329

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0609009
 http://arxiv.org/abs/math/0609009

Collections

arXiv