I’ve written before about a knight’s random walk on an ordinary chess board. In this post I’d like to look at the generalization to **three dimensions** (or more).

So what do we mean by 3D chess? For this post, we’ll have a three dimensional lattice of possible positions, of size 8 by 8 by 8. You could think of this as a set of 8 ordinary chess boards stacked vertically. To generalize a knight’s move to this new situation, we’ll say that a knight move consists of moving 2 steps in one direction and 1 step in an orthogonal direction. For example, he might move up two levels and over one position horizontally.

Suppose our knight walks randomly through the chess lattice. At each point, he evaluates all possible moves and chooses one randomly with all possible moves having equal probability. How long on average will it take our knight to return to where he started?

As described in the post about the two dimensional problem, we can find the average return time using a theorem about Markov chains.

The 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 2

N/kwhereNis the number of edges in the graph, andkis the number of edges meeting at the starting point.

The problem reduces to counting *N* and *k*. This is tedious in two dimensions, and gets harder in higher dimensions. Rather than go through a combinatorial argument, I’ll show how to compute the result with a little Python code.

To count the number of edges *N*, we’ll add up the number of edges at each node in our graph, and then divide by 2 since this process will count each edge twice. We will iterate over our lattice, generate all potential moves, and discard those that would move outside the lattice.

from numpy import all from itertools import product, combinations def legal(v): return all([ 0 <= t < 8 for t in v]) count = 0 for position in product(range(8), range(8), range(8)): # Choose two directions for d in combinations(range(3), 2): # Move 1 step in one direction # and 2 steps in the other. for step in [1, 2]: for sign0 in [-1, 1]: for sign1 in [-1, 1]: move = list(position) move[d[0]] += sign0*step move[d[1]] += sign1*(3-step) if legal(move): count += 1 print(count // 2)

This tells us that there are *N* = 4,032 nodes in our graph of possible moves. The number of starting moves *k* depends on our starting point. For example, if we start at a corner, then we have 6 possibilities. In this case we should expect our knight to return to his starting point in an average of 2*4032/6 = 1,344 moves.

We can easily modify the code above. To look at different size lattices, we could change all the 8’s above. The function `legal`

would need more work if the lattice was not the same size in each dimensions.

We could also look at four dimensional chess by adding one more range to the position loop and changing the combinations to come from `range(4)`

rather than `range(3)`

. In case you’re curious, in four dimensions, the graph capturing legal knight moves in an 8 by 8 by 8 by 8 lattice would have 64,512 edges. If our knight started in a corner, he’d have 12 possible starting moves, so we’d expect him to return to his starting position on average after 5,275 moves.

The combinatorial argument need not be that complicated, depending on how you do it. Rather than asking “How many moves can we make from each space?” we can ask “From how many spaces can we make a move in this direction?” The move (0, 1, 2) can be made from a space with any x-coordinate, any y-coordinate except 8, and any z-coordinate except 7 and 8, for a total of 8 * 7* 6 = 336 spaces. By symmetry, any other move can also be made from 336 spaces. Multiply by the 3! * 4 possible moves, then divide by 2 for double counting, and you get 4032. This argument can easily be generalized to any dimension. Of course, one drawback of this method is that it does not tell you much about the distribution of the N, whereas the Python code in this post could easily be modified to do so.

For what it’s worth, here’s a working numpy version (also done as a more coherent generator comprehension, which I find more illustrative than the staircased version):