Counting Knight's Tours through the Randomized Warnsdorff Rule

Details Counting Knight's Tours through the Randomized Warnsdorff Rule Counting Knight's Tours through the Randomized Warnsdorff Rule

2006-08-31

arxiv.org/abs/math/0609009v1

Mathematics

Probability

8 pages. See also http://www.cmat.edu.uy/~mordecki/articles

Scientific paper

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}$.

Affiliated with

Also associated with

No associations

Rating

Counting Knight's Tours through the Randomized Warnsdorff Rule does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting Knight's Tours through the Randomized Warnsdorff Rule, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Knight's Tours through the Randomized Warnsdorff Rule will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-492553