Solutions to knight's random walk

Solutions to knight's random walk
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.

# 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)

https://github.com/thomas-scrace/Knight-Random-Walk/blob/master/knights_random_walk.py
Read full article from Solutions to knight's random walk