2006/08/31 by Héctor Cancela, Ernesto Mordecki, Cancela, Héctor +1
Computer Science · Mathematics · #Advanced Database Systems and Queries #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Probability (math.PR) #Probability and Statistical Research #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.math/0609009
8 pages. See also http://www.cmat.edu.uy/~mordecki/articles
arxiv created 2006/08/31 · openalex publication_date 2006/08/31 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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× 1015.