A knight’s random walk  Here’s a puzzle I ran across today:
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?  There’s
a slick mathematical solution that I’ll give later.  You could
also find the answer via simulation: write a program to carry
out a knight random walk and count how many steps it takes.
Repeat this many times and average your counts.   Related post:
A knight’s tour magic square  38 thoughts on “A knight’s random
walk    1. def move_knight(start_point, step_til_now)     if
start_point == [0, 0] and step_til_now != 0 then return
step_til_now end     next_points = [     [2, 1],     [-2, 1],
[2, -1],     [-2, -1],     [1, 2],     [1, -2],     [-1, 2],
[-1, -2]     ].map{|x| [start_point[0] + x[0], start_point[1] +
x[1]]}     .select{|x| x[0] >= 0 and x[0] =0 and x[1] < 8}
return move_knight(next_po