The New York Times has a daily puzzle named Tiles that works as follows. Start with $m$ squares (in the official version, this is 30, in a 6x5 grid), and a set of $p>4$ possible patterns (typically this is a dozen or so, but the precise number doesn't matter). Each square contains 4 of the $p$ patterns (although this can be generalized as well).
The rules of the game are that you start at any square and then move to any other square that contains at least one of the patterns in your start square. When you choose that next square, the overlapping patterns disappear from both squares. So if you start at a square with patterns $\{a,c,e,g\}$ and move to one with patterns $\{a,b,c,d\}$, then the first square is now reduced to having $\{e,g\}$ left in it and the second square has $\{b,d\}$. You must then find a square with at least one of $b$ or $d$ in it, and so on until all the squares are empty. If the second square is empty after you move to it, you may select any square with at least one pattern and continue from there. The number of instances of any pattern $p$ in the puzzle across all squares is always even, thus guaranteeing that a solution exists.
The challenge in the actual game is visual, being able to spot matching patterns across squares. But there is an interesting combinatoric/graph theory problem as well. By switching the order in which you visit the squares, you can complete the puzzle in a greater or lesser number of moves. For instance, if there four squares with the patterns:
1 2 3 4
================
a a a a
b b
c c
d d
e e
Then the puzzle can be cleared by going through the sequence $1\rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4$, for a total of 7 moves. Or it can be solved in 5 moves with $1\rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 1$.
The question is, then, given the set of patterns in each square, what is the most efficient way to determine the shortest and longest paths that solve the puzzle?
