Unkown Blogger Pursues a Deranged Quest for Normalcy

• Blog Stats

• 10,700 hits

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