# A New York Times tiles-based graph theory question

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?

• It seems like this could be an NP-hard problem. But I don't immediately see a reduction from a known NP-complete problem. – Timothy Chow Oct 3 '20 at 15:07
• I thought that the problem has an interesting graph structure to it, with multiple connections between points, and you have to find a complete circuit around the graph. This isn't something that's been solved yet? – David Pepper Oct 4 '20 at 20:37
• Some special cases have been solved. For example, suppose that for any two tiles that share a pattern, they share exactly one pattern, and that pattern doesn't appear anywhere else. Then (if I understand the rules correctly) finding a single sequence that erases all the patterns is equivalent to finding an Eulerian trail, which can be done efficiently. But Tiles allows two tiles to share more than one pattern, and for a pattern to appear multiple times. Maybe this is equivalent to a known problem, but I don't recognize it. – Timothy Chow Oct 4 '20 at 22:37
• Note in particular that if A, B, C, and D all share a pattern, then initially, one can proceed directly between any two of these tiles. But if one chooses to go from A to B (say), then the pattern disappears, and it is no longer possible to go from A or B directly to C or D (unless some other pattern is shared). This feature differentiates the problem from the Eulerian trail problem and is part of what makes me suspect that it may be NP-hard. – Timothy Chow Oct 6 '20 at 12:00
• Maybe Hamiltonin path on a 3-regular graph reduces to this with a bit of work? – Ville Salo Feb 6 at 7:25