Imagine matching dominoes end-to-end such that only like numbers are joined. For a collection of dominoes, one could ask whether it is possible to join them all into a single strand.
I'm interested in a slightly different problem. What if dominoes could be translated but not rotated? That is, [2 | 3] is distinct from [3 | 2] so there are $n^2$ dominoes with numbers up to $n$ rather than ${n\choose2}+n$ dominoes. In particular, for a given multiset of dominoes (a non-negative integer-valued $n\times n$ matrix, if you prefer), is it possible to choose an order such that the second and first numbers, respectively, of adjacent dominoes are equal? (The first number of the first domino need not equal the second number of the last domino: they are in a line not a ring.)
I'd also be interested in related questions:
- the number of solutions (if there are solutions)
- an algorithm for finding a solution (if there are solutions)
- the length of a maximal solvable submultiset (if there are no solutions)
- an algorithm for finding a maximal solvable submultiset (if there are no solutions)
if anyone has a reference (or is looking for brownie points).
Clarification: I do not have all $n^2$ dominoes, but a multiset of dominoes. Some appear more than once, others (most!) do not appear at all.