My previous post asked this question:
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 is a mathematical solution that is a little arcane, but short and exact. You could also approach the problem using simulation, which is more accessible but not exact.
The mathematical solution is to view the problem as a random walk on a graph. The vertices of the graph are the squares of a chess board and the edges connect legal knight moves. The general solution for the time to first return is simply 2N/k where N is the number of edges in the graph, and k is the number of edges meeting at the starting point. Amazingly, the solution hardly depends on the structure of the graph at all. It only requires that the graph is connected. In our case N = 168 and k = 2.
For a full explanation of the math, see this online book, chapter 3, page 9. Start there and work your way backward until you understand the solution.
And now for simulation. The problem says to pick a legal knight’s move at random. The most direct approach would be to find the legal moves at a given point first, then choose one of those at random. The code below achieves the same end with a different approach. It first chooses a random move, and if that move is illegal (i.e. off the board) it throws that move away and tries again. This will select a legal move with the right probability, though perhaps that’s not obvious. It’s what’s known as an accept-reject random generator.
from random import randint
# Move a knight from (x, y) to a random new position
def new_position(x, y):
while True:
dx, dy = 1, 2
# it takes three bits to determine a random knight move:
# (1, 2) vs (2, 1), and the sign of each
r = randint(0, 7)
if r % 2:
dx, dy = dy, dx
if (r >> 1) % 2:
dx = -dx
if (r >> 2) % 2:
dy = -dy
newx, newy = x + dx, y + dy
# If the new position is on the board, take it.
# Otherwise try again.
if (newx >= 0 and newx < 8 and newy >= 0 and newy < 8):
return (newx, newy)
# Count the number of steps in one random tour
def random_tour():
x, y = x0, y0 = 0, 0
count = 0
while True:
x, y = new_position(x, y)
count += 1
if x == x0 and y == y0:
return count
# Average the length of many random tours
sum = 0
num_reps = 100000
for i in xrange(num_reps):
sum += random_tour()
print sum / float(num_reps)
A theorem is better than a simulation, but a simulation is a lot better than nothing. This problem illustrates how sometimes we think we need to simulate when we don’t. On the other hand, when you have a simulation and a theorem, you have more confidence in your solution because each validates the other.
