## Knight’s tour revisited

Posted by ubpdqn on May 13, 2012

Once again I have found food for thought in a post on John D Cook’s blog.

The puzzle posed:

*Start a knight at a corner square of an otherwise-empty chessboard. Move the knight at random by choosing uniformly from the legal knight-moves at each step. What is the mean number of moves until the knight returns to the starting square?*

As is discussed this can be solved by considering a random walk on the Knight’s tour graph (connected graph).

I found it instructive to count the edges of the Knight’s tour graph (though I am disappointed that it was not as ‘clear’ to me as suggested). Consider the $latex n\times n$ chessboard. The sum of the degrees of all the vertices is twice the number of edges.

Consider the following 6 $latex \times$ 6 board. The color represent distinguishes the degree of the vertices.

Using insights from this chessboard, see the…

View original post 303 more words

## Leave a Reply