What is the probability of traversing through an $n \times n$ board in exactly $K$ moves by moving uniformly at random? On a $n$-row $n$-column board, we want to move a piece from the square on the lower left corner to the square on the upper right corner following the commands of a light that blinks in $3$ different colors:


*

*Each color represents a move: up, right, or diagonal (up and to the right) .

*The probability of each one blinking is equal.


What is the probability of reaching the square in the upper right corner using $K$ moves, knowing that when the piece reaches a square that it's impossible to make $1$ of the $3$ moves, that color stops blinking?
 A: The solution was corrected in accordance with the explanations of the task condition contained in the leonbloy comments.
It turns out to be very cumbersome, but to get the calculation formulas had to take into account a lot of details. For convenience, we assume 
that the board has the size $ (n + 1) \times (n + 1) $ and the board's cells are denoted by the pair of coordinates  $ (u, v), u, v \in \lbrace 0, 1, \dots, n \rbrace. $
First, we determine the probability  $ P (u, v, t) $  of the moving of the chip from the initial position  $ (0,0) $  to the position  $ (u, v) $  in $  t $  steps for  $ u, v \le n-1 $.
Let  $ i, j, d $  be the number of moves to the right, up and diagonally, respectively. Obviously:
$ i+j+d=t, i+d=u, j+d=v, $
from where $u+v-t=d,  i=u-d=t-v,  j=v-d=t-u,$ and   $ u  \le t, v \le t  \le u+v.$
Then
(1) $P(u,v,t)=\frac 1 {3^t} C_t^{i}C_{t-i}^j=\frac 1 {3^t} C_t^{v}C_{v}^{t-u},$
where $ C_t ^ {i}$  is the number of variants of moving to the right,$  C_ {v}^ {t-u}$  is the number of variants of moving up, $ C_t^{v} C_{v}^{t-u} $  is the number of routes of length $ t $  from the initial position to the position  $ (u, v), \frac 1 {3 ^ t} $  is the probability of choosing each of these routes.
Next, we determine the probability  $ P'(n, v, t) $  of the first chip exit to the boundary  $ (n, v) $  in  $ t  $ steps.
This exit is possible  with probability $  1/3 $  from position  $ (n-1, v)$ and from position  $ (n-1, v-1)$ for  $ v \ge 1 $ .
Therefore
$ P'(n,0,t)= \frac 13 P(n-1,0,t-1),   $ 
$ P'(n,v,t)= \frac 13 [P(n-1,v,t-1)+ P(n-1,v-1,t-1) ]$  for  $  1 \le v \le n-1 $. 
Similarly, for the first exit of the chip on the boundary  $ (u, n) $, we can write:
$ P'(0, n, t) = \frac 13 P(0, n-1, t-1),$
$ P'(u, n, t) = \frac 13 [P(u, n-1, t-1) + P (u-1 , N-1, t-1)]  $ for  $ 0 \le u \le n-1. $ 
And for the first exit to the right and upper bounds at (n, n):
$ P'(n, n, t) = \frac 13 P(n-1, n-1, t-1). $ 
After the first exit to any boundary, the movement of the chip is determined with probability 1,
The chip will move from the starting position to the position  $ (n, n) $  through the first exit to the border at position  $ (n, v) $  in  $ k $  steps, if to the position  $ (n, v) $  it moved  $ t_v = k + v-n $  steps (similarly for positions  $ (u, n) $ ), therefore
$ P(n, n, k) = \sum_{v = 0}^{n-1} P'(n, v, t_v) + \sum_{u = 0}^{n-1} P'(u, N, t_u) +\frac 13  P(n-1, n-1, k-1) $ ,
where  $ t_v = k + v-n, t_u = k + u-n. $ 
Taking into account the equality of the written sums, we can write
$ P (n, n, k) = 2 \sum_{v = 0}^{n-1} P'(n, v, t_v) + \frac 13  P (n-1, n-1, k-1) =$
$  =\frac 23  P(n-1,0, k-n-1) + \frac 13  P(n-1, n-1, k-1) + 2 \sum_{v = 1}^{n-1} P'(n , v, k + v-n) = $ 
$ = 2 \frac {J (k = 2n)} {3 ^ {n}} + \frac 13  P(n-1, n-1, k-1) +$
$+ \frac 23\sum_{v = 1}^{n-1} [P(n-1, v, k + v-n-1) + P (n-1, v-1, k + v-n-1)] $ 
where  $J (\cdot)$ is the indicator of true, probabilities $P (u, v, t)$ are defined by (1).
To check the obtained formulas, I calculated the probability values $ P (n, n, k) $ for  $n = 6 $ (board 7x7), which for $ k = 6, 7, \dots, 12 $ are equal:  0.00137, 0.03018, 0.15546, 0.32109, 0.31550, 0.14896, 0.02743. To my great surprise, the results fully coincided with the results of Andrew Woods, given in his reply.
