The problem is a Markov chain, and we can attack it with linear algebra!
First, we can simplify the problem by exploiting the symmetry of both the knight's movement and the chessboard. Let's add the following rule:
- After every move, the knight is reflected across the horizontal, vertical, and diagonal axes of symmetry, until it rests in the upper-left triangle of $10$ squares.
In other words, the legal positions are 1a, 1b, 1c, 1d, 2b, 2c, 2d, 3c, 3d, and 4d. You can visualize these positions as occupying one of the $8$ triangles in this diagram:
Now, there are $11$ positions that the knight can occupy after a move: the $10$ positions just named, and $1$ position representing not-on-the-board. For $i,j\in[1,11]$, let $P_{i,j}$ be the probability of transitioning from $i$ to $j$. There are $11\times11=121$ probabilities to calculate, and I suspect that this part must be done by hand.
Now we have an $11\times11$ square matrix $P$. For all $n$, the matrix power $P^n$ is the transition matrix for $n$ moves! So, let's arbitrarily index the initial square as $i=1$ and the off-the-board position as $j=11$. Then the probability of leaving the board after $n$ moves is $(P^n)_{1,11}$, and the probability of staying on the board is:
$$1-(P^n)_{1,11}$$
That's as far as I can take you. You could express this formula more explicitly by calculating $P$ and then finding its Jordan normal form. Then you'll have a formula for the powers $P^n$, and you can pull out whatever matrix element you want. If you've seen the explicit formula for the Fibonacci numbers, it's the same principle, but with a larger matrix!
Edit: You've commented that if the knight is in the center of the board, then it can't exit the board in $1$ move. This is a useful obvservation. If we index positions 3c, 3d, and 4d as $i=8,9,10$, then it tells us that $P_{8,11}=P_{9,11}=P_{10,11}=0$. So you see, the matrix $P$ can represent pretty much everything we know about the problem.
Another example of reading information from $P$: You have a rule that if the knight leaves the board, it can't come back. This translates to the statement that $P_{11,11}=1$, and for all $j<11$, $P_{11,j}=0$. Between this paragraph and the previous paragraph, we already know $14$ matrix elements. There are just $107$ more to calculate...
Edit 2: Another example. You commented that from the initial position, only $2$ out of $8$ possible moves stay on the board. That tells us that $P_{1,11}=3/4$. The knight can stay on the board by moving to 2c or 3b. In my scheme, 3b gets reflected back to 2c. So if we index 2c as $j=6$, then $P_{1,6}=1/4$. For all other $j$ besides $6$ and $11$, we have $P_{1,j}=0$. That's another $11$ matrix elements calculated; $96$ to go...
An exact computation to answer question 1. is simple in principle, difficult to do exactly with no computer, and the result is frankly not very interesting. Question 2. is more interesting since, after 3600 steps on a graph of 25 vertices with diameter 10, the random walk is close to its stationary distribution.
The random walk is equivalent to the simple reversible random walk on the augmented graph where one adds 3 supplementary loops to each corner, 2 to each side vertex not a corner, and 1 to each other vertex. Every vertex in the augmented graph has degree 5 hence the stationary distribution is uniform. The Markov chain is aperiodic hence, at any large time, the probability to be at any of the vertices of this graph with 25 vertices is approximately 1/25.
The probability to be in any set S of vertices is approximately the size of S divided by 25. There are 4 corners hence the probability to be at one corner is approximately 4/25. There are 16 side squares hence the probability to be on one side is approximately 16/25.
Best Answer
Thanks for the interesting and creative problem.
It made me curious as to how large the path could get for Energy = 20, so I mapped it:
The origin is the green cell and the possible end cells are yellow. The cells that your question asks for percentages on are the orange squares.
With problems like these with a gajillion possibilities, I lean heavily toward using a simulator.
I ran 4 simulations, each for 100 million trials, and since all 4 of them gave similar results, I concluded that the number of trials for each run was large enough. Here are the results:
------------------------ Original answer end ------------------------
Edit: This may be overkill, but I was curious how many distinct stopping points there were, and I wanted to see how the probabilities decreased as the endpoint got further from the origin.
So, I altered the sim again and re-ran it for 2,147,483,646 runs, and here are those results. The percentages are out of all possible paths, not just for the white slice shown. I am showing only the slice because it considers all 161 distinct points (and makes it small enough to read, but you'll probably need to save it to your machine to view it). All other possible ending points are a reflection of these points.
Quite a few possible ending points far from the origin were never hit once, and some were hit only once (15,10; 16,7; and 17,0)