What algorithm to use to generate random path of given length
Algo for solving problem when path self-intersections are allowed

Auxiliary problem

First let's solve another problem: 


  How many paths of length $K$ exists starting at coordinate $(StartRow, StartColumn)$.


Such problem can be solved by dynamic programming: let $dp[K][R][C]$ be answer for question:


  How many paths of length $K$ exists that start in $(StartRow, StartColumn)$ and ends in $(R, C)$".


Base case:
$$
dp[0][StartRow][StartColumn] = 1 
$$

Step of dynamic:
$$
dp[K][R][C] = dp[K-1][R-1][C] + dp[K-1][R+1][C] + dp[K-1][R][C-1] + dp[K-1][R][C+1]
$$

Here we suppose $dp[K][X][Y]=0$, for any $X$ and $Y$ that outside of grid (e.g. $X &lt; 1$ or $X &gt; N$ or $Y &lt; 1$ or $Y &gt; N$)
Also we can even add more constraints for problem and add obstacles: for doing so - we need to suppose $dp[K][R][C]=0, \forall K$, where cell $(R, C)$ is impassable (e.g. is obstacle).

This will take $O(N*M*K)$ time, where $N$ - number of rows, $M$ - number of columns, and $O(N*M*K)$ memory if we will keep all steps of dynamic or $O(N*M)$ if we will keep only last step of dynamic.

Original problem


  Generate random path of length $K$ between cells $S(R_s, C_s)$ and $E(R_e, C_e)$.



First of all we need count how many paths of length $K$ exists between this cells, for that we can use previously described dynamic:
futhermore run it from end cell (e.g. count how many paths of length $K$ exist that start at $(R_e, C_e)$) and save all step of dynamic (we will use it in next steps).
Now add order relation between all paths of length $K$ starting at cell $(R, C)$ and ending at cell $E(R_e, C_e)$: 


if $K=0$ we have $0$ or $1$ such paths (such collection is always ordered);
if $K&gt;0$ let's suppose: Paths that go UP $&lt;$ Paths that go RIGHT $&lt;$ Paths that go DOWN $&lt;$ Paths that go LEFT (and for ordering paths in each of 4 groups we can recursevly apply this definition again).

Then we know how many paths of length $K$ exist between cells $S$ and $E$, lets name it $A=dp[k][R_s][C_s]$, now we can uniformly at random peek number $L\in[0, A)$ that will identify choosen path among all $A$ available.
We had ordered all $A$ paths and choose some path to output $L$ ($0-indexed$) and just need to find it. Let $choose(R_c, C_c, L, K)$ - function that return $Lth$ path of length $K$ staring at cell $(R_c, C_c)$ and ending at $E(R_e, C_e)$:


$$
 choose(R_c, C_c, L, K) =\small\left\{
                \begin{array}{ll}
                  \langle empty \rangle, K = 0\\
                  \langle UP, choose(R_c - 1, C_c, L - 0, K - 1)\rangle,
                  \\ \hspace{45pt} L \in [0, Count_u)\\
                  \langle RIGHT, choose(R_c, C_c + 1, L - Count_u, K - 1)\rangle, 
                  \\ \hspace{45pt} L \in [Count_u, Count_u + Count_l)\\
                  \langle DOWN, choose(R_c + 1, C_c, L - (Count_u + Count_l), K - 1)\rangle, 
                  \\ \hspace{45pt} L \in [Count_u + Count_l, Count_u + Count_l + Count_d)\\
                  \langle LEFT, choose(R_c, C_c - 1, L - (Count_u + Count_l + Count_d), K - 1)\rangle, 
                  \\ \hspace{45pt} L \in [Count_u + Count_l + Count_d, A)\\
                \end{array}
              \right.\\
$$
$$
Where \forall K, R_c, C_c\\
Count_u=dp[K - 1][R_c - 1][C_c]\\
Count_l=dp[K - 1][R_c][C_c + 1]\\
Count_d=dp[K - 1][R_c + 1][C_c]\\
Count_r=dp[K - 1][R_c][C_c - 1]\\
$$

And $Count_u$ means how many paths of length $K$ starts at $(R_c, C_c)$ and ends at $(R_e, C_e)$ and first move is $UP$, $Count_l$, $Count_d$, $Count_r$ defines respectively for another directions.

More intuitively, imagine we at $X$ cell choosing for $7th$ path:


...
_   4   _
5   X   0
_   9   _
...


If we go $UP$ we will follow paths $\in [0, 4)$, there is no paths to $RIGHT$, if we go $DOWN$ we will follow paths $\in [4, 4+9)$, so we need to go $DOWN$ and choose $(7 - 4)th$ path among all that starts in that cell.

Note: due to we define ordering on paths $I'th$ path everytime will be the same (so it's possible to store path just as index number among all such paths and restore path when it is needed). Also need to notice that order $UP &lt; RIGHT &lt; DOWN &lt; LEFT$ is not only right choise, you can use any order - just keep it thorugh all algorithm flow the same.