## Use Julia

`library(JuliaCall)`

Solved with Julia

Riddles

Author

Jonatan Pallesen

Published

August 23, 2019

From the Riddler book.

Suppose that a knight makes a random walk on an infinite chessboard. Specifically, every turn the knight follows standard chess rules and moves to one of its eight accessible squares, each with probability 1/8.

What is the probability that after the twentieth move the knight is back on its starting square?

The knight moves two tiles in any direction, and one tile in a direction perpendicular to that.

Here are the 8 moves:

The function *take_twenty_random_moves* moves the knight 20 times at random, and returns the position the knight end up at.

We do this a number of times, and record how many of those times it ended up back at the starting point.

```
using Random
Random.seed!(0);
nsims = 10^6;
take_twenty_random_moves() = Tuple(sum(hcat(rand(moves, 20)...), dims = 2));
sum(take_twenty_random_moves() == (0, 0) for _ in 1:nsims) / nsims
```

`0.006266`

This is solved via recursion. After each move, the first number in the vector counts the number of possible ways to return to the starting position from there, while the second number in the vector counts the total number of possible moves from there.

The solution is then found by dividing the first number by the second.

(The coordinates of the position *i* and *j* are used instead of the position as a tuple, in order for the memoize function to be able to efficiently remember all the positions it has already seen.)