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