It seems that because you are only using the counts for number of cycles in a graph to randomly choose a cycle, that if you had a random approximation for this number, then you could still choose a cycle approximately uniformly.

Note that the number of cycles in a graph $G$, which contains edge $(u, v)$, equals the number of cycles in $G - (u, v)$ plus the number of simple paths from $u$ to $v$ in $G - (u, v)$. Thus, with a polynomial time approximation for the number of $u$-$v$ paths, the a polynomial time approximation can be achieved by incrementally building up to $G$ one edge at a time, approximating as you go.

I actually think that there's a more straightforward method for choosing a cycle. Let $G$ be the entire graph of edges around the $n \times n$ grid of squares. For each edge $(u, v)$ find the number of cycles containing that edge (which is the number of $u$-$v$ paths in $G$ - $(u, v)$). Then randomly choose an edge weighted by the number of cycles that contain it. This will be the first edge in your randomly chosen cycle. All other edges will be chosen by extending one edge at a time.

Assume that you have chosen a path which is part of your random cycle. Let the set of vertices on this path be $C$ and let $v_s$ and $v_e$ be the endvertices of the path. Also let $N$ be the set of neighbors of $v_e$ which are not in $C$ (note that there are only up to 3 in this particular graph). For each $u \in N$ count the number of $u$-$v_s$ paths in the induced graph $G[V - (C - \{v_s, v_e \} ) ]$. Then choose a neighbor, $u$, of $v_e$ weighted on the paths just counted. Add the edge $(v_e, u)$ to your chosen path, extending it by one.

In this way, a polynomial number of edges are chosen, each requiring a small number of calculations of a polynomial time approximation algorithm. Thus, a cycle can be uniformly chosen.

I currently have a stackexchange question requesting references for fast path count approximation algorithms. I've read in a few places that these algorithms exist but haven't yet found them.

It seems that because you are only using the counts for number of cycles in a graph to randomly choose a cycle, that if you had a random approximation for this number, then you could still choose a cycle approximately uniformly.

Note that the number of cycles in a graph $G$, which contains edge $(u, v)$, equals the number of cycles in $G - (u, v)$ plus the number of simple paths from $u$ to $v$ in $G - (u, v)$. Thus, with a polynomial time approximation for the number of $u$-$v$ paths, the a polynomial time approximation can be achieved by incrementally building up to $G$ one edge at a time, approximating as you go.

I actually think that there's a more straightforward method for choosing a cycle. Let $G$ be the entire graph of edges around the $n \times n$ grid of squares. For each edge $(u, v)$ find the number of cycles containing that edge (which is the number of $u$-$v$ paths in $G$ - $(u, v)$). Then randomly choose an edge weighted by the number of cycles that contain it. This will be the first edge in your randomly chosen cycle. All other edges will be chosen by extending one edge at a time.

Assume that you have chosen a path which is part of your random cycle. Let the set of vertices on this path be $C$ and let $v_s$ and $v_e$ be the endvertices of the path. Also let $N$ be the set of neighbors of $v_e$ which are not in $C$ (note that there are only up to 3 in this particular graph). For each $u \in N$ count the number of $u$-$v_s$ paths in the induced graph $G[V - (C - \{v_s, v_e \} ) ]$. Then choose a neighbor, $u$, of $v_e$ weighted on the paths just counted. Add the edge $(v_e, u)$ to your chosen path, extending it by one.

In this way, a polynomial number of edges are chosen, each requiring a small number of calculations of a polynomial time approximation algorithm. Thus, a cycle can be uniformly chosen.

I currently have a stackexchange question requesting references for fast path count approximation algorithms. I've read in a few places that these algorithms exist but haven't yet found them.