If I'm understanding properly, you are adding edges to change the simple undirected grid graph G(m,n) into an undirected multigraph with an Eulerian circuit.

If this is the case then you need to find an optimal way to add edges such that every vertex has even degree, which is a necessary and sufficient condition for an Eulerian circuit's existence.

Were you working along these lines and unable to spot a pattern? Or were you working along some other lines?