  In this paper, we provide a family of dynamic programming based algorithms to
sample nearly-shortest self avoiding walks between two points of the integer
lattice $\mathbb{Z}^2$. We show that if the shortest path of between two points
has length $n$, then we can sample paths (self-avoiding-walks) of length
$n+O(n^{1-\delta})$ in polynomial time. As an example of an application, we
will show that the Glauber dynamics Markov chain for partitions of the Aztec
Diamonds in $\mathbb{Z}^2$ into two contiguous regions with nearly tight
perimeter constraints has exponential mixing time, while the algorithm provided
in this paper can be used be used to uniformly (and exactly) sample such
partitions efficiently.
