Problem $3$

Suppose we have a $mn$ grid $(m$ squares one way, $n$ squares the other$),$ and some squares of the grid $(q$ of

them$)$ are colored green while all the others are uncolored. We wish to cover the green squares with dominoes,

which are $12$ or $21$ subgrids. The dominoes may overlap $($share squares$)$ but they may not be placed so

as to cover any uncolored squares.

A green walk starts at a green square $s_1,$ then moves to an adjacent green square $s_2,$ then to a green

square $s_3$ adjacent to $s_2,$ etc., up to a green square $s_k$ for some positive $k>1.$ A green walk may visit

a square more than once: it is possible that $s_i=s_j$ for $ij.$ A green walk is non$-$backtracking if$,$ upon

stepping from any $s_i$ to $s_{i+1},$ we do not immediately step back to $s_i.$ That is$,s_i{s}_{i+2}$ for any i between $1$

and $k-2,$ inclusive. A non$-$backtracking green walk is called a green tour if $s_1=s_k$ and $k>1.$

Assume that the green squares that you are given contain no green tours.

Under this condition, find an efficient algorithm that covers all of the green squares using the minimum

number of dominoes. The running time may be a function of $m,n,$ or $q,$ or some combination of these

variables.

Note that if there is a green square that is not adjacent to any other green square, then this type of

covering is not possible, and the algorithm should report this.