Generating a random path in a grid without deadlock I want to write an algorithm that takes an $n \times n$ grid and a number $L$, generate a random walk of length $L$ on the grid that doesn't visit the same cell twice.

One simple solution would be keep randomly choosing a neighbour of the last cell to add to the path. I found that for small density (i.e. $L &lt; 0.625n^2$), I can repeat this algorithm a large amount (at least $1000$) times and can almost find some complete path without deadlock, i.e. without a a state where the path is incomplete but there is no more move available (i.e. all neighbours of the current cell is already filled). A DFS can lead to a deadlock state, and from my experiments, most of the end states are deadlocks, hence it is very hard to get to a complete state with DFS. But for larger density, it is nearly impossible to avoid deadlock no matter how many times I repeat.

My second attempt is to backtrack one step if the current $i^{th}$ step results in a deadlock (i.e. delete the last action from the list of possible actions at $(i-1)^{th}$ step and randomly choose a remaining action to retry). However it apparently took forever to finish the path (it kept going forward and backward when $i$ reaches $0.625n^2$).

Is there any suggestion for a fast algorithm that have fairly high probability of avoiding deadlocks? I'm fine with pseudo-randomness.
You have a solid grid graph, and want to generate a random Hamiltonian path in it.  The following paper describes a polynomial-time algorithm to generate such a path, randomly (from a distribution that is close to uniform):

Self-testing algorithms for self-avoiding walks. Dana Randall, Alistair Sinclair. Journal of Mathematical Physics, vol 41 no 3, pp. 1570–1584, 2000.

Be warned that the algorithm is fairly complex.

Here is a more recent paper that also proposes an algorithm to solve this problem:

Secondary Structures in Long Compact Polymers.  Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen, Jane' Kondev.  arxiv.org:cond-mat/0508094

On cursory inspection, it looks like it might be easier to implement.



Other related work that might possibly be of interest:

The following paper proposes an algorithm to count the number of such Hamiltonian paths:

A matrix method for counting hamiltonian cycles on grid graphs.  Y. H. Harris Kwong, D. G. Rogers.  European Journal of Combinatorics, vol 15 no 3, pp.277-283, 1994.

I found a reference that claims that the following paper describes 

Enumeration of tours in Hamiltonian rectangular lattice graphs.  Basil R. Myers.  Mathematics Magazine, vol 54, no 1, Jan 1981.

Often, if you can count the number of objects of a particular type, you can sample uniformly at random from the set of such objects.  So, that would be a good starting point to look, if you don't like either of the two papers mentioned above.

The following paper describes how to find a Hamiltonian path of such a solid grid graph (but with no guarantees of any particular random distribution on the output): 

Hamiltonian Cycles in Solid Grid Graphs.  Christopher Umans, William Lenhart.  FOCS 1997.

See also https://mathoverflow.net/q/1592/37212, https://stackoverflow.com/q/7371227/781723, Hamiltonian path in grid graph.