Count paths of length $n$ that a player can take
This is a question in combinatorics, and can be calculated in a closed formula.

The key settings are:


"Down" is not allowed
Visiting previously visited square is not allowed


From the two requirements, we can draw the following conclusions:


Up is always a valid move (since we never went down, going up is essentially revealing a new square)
Left is not valid after Right, but is valid after Up (revealing new row) or after Left (which is essentially unvisited)
Right is not valid after Left, but is valid after Up (revealing new row) or after Right (which is essentially unvisited)


Denote $U$, $L$ and $R$ for Up, Left and Right respectively. We can now represent a path in a string like so: $P = (U,U,U,U,L)$

The question is now: How many valid paths strings of length $n$ are there?



Let $T(n)$ be the number of valid strings of length $n$


If the first move is $U$ then the remaining strings are $T(n-1)$
If the first move is $L$ then the remaining strings are those starting with $L$ or $U$
If the first move is $R$ then the remaining strings are those starting with $R$ or $U$


Looking at strings where the first move is either $L$ or $R$: the remaining strings are: strings starting with $U$ (twice), starting with $L$, or starting with $R$. (simple summation of all the options in 2nd and 3rd bullet).

Note that all the strings starting with $U$ + all the strings starting with $L$ + all the strings starting with $R$ is exactly $T(n-1)$ since the first move is already set.

We are left with one more instance of "all the strings starting with $U$" = $T(n-2)$ (again, first move is set)

Which results the following recursive formula: $$T(n) = 2T(n-1)+T(n-2)$$
where:

$$T(1) = 3, \space
T(2) = 7 $$



Calculations omitted, the closed formula for the relation above is:

$$T(n)= \frac{(1+\sqrt{2})^{n+1}}{2} + \frac{(1-\sqrt{2})^{n+1}}{2} $$