Non-rotatable dominoes 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.
I don't quiet like @RossMillikan's answer since it reduces to a hard problem (Hamiltonian path!). Here is another reduction to an easier question: Eulerian path in the directed multi-graph (if you want your non-rotation condition and allow repeated dominos).

If you dominos have ends numbered from $1$ to $n$, then create a graph on $n$ vertices. If a domino is labeled $[x | y]$ then add the directed edge $(x,y)$ to your graph (add multiple edges if the domino appears multiple times). To make a chain you need to find a Eulerian path in this graph (if you want your dominos to form a circle, then you need a Eulerian cycle). Further, note that the reduction in the opposite direction works too, every dircted multigraph can be encoded as a dominos problems. Thus this question is equivalent to the Eulirean path problem, and hence a reference is the literature on Eulerian paths.

If you said domino could only appear once, then the graph would not be a multi-graph. If you said we could rotate dominos, then the graph would be undirected.

How do you check if a multi-graph has a Eulirean path? If you have a set (instead of a multi-set) of dominos or in terms of graphs you have a directed multi-graph then the condition is simple:


The graph is connected
And each vertex has the same in-degree and out-degree. With the possible except of two vertexes with one having one more in-degree than out-degree and the other having one more out-degree than in-degree.
There are always many solutions.  You can think of it as a directed graph.  Each domino is a vertex.  There is a path from vertex $A$ to vertex $B$ if domino $B$ can follow $A$ in the chain.  Each domino has $n$ incoming paths and $n$ outgoing paths, and you are looking for a Hamiltonian path.  One way to prove it possible is by induction.  It works for $n=1$ as there is only one domino.  Given a solution for $n$, create a solution for $n+1$ by joining all dominoes $[a,n+1]$ to $[n+1,a]$ to make a new $[a,a]$.  These can be inserted anywhere in the chain where there is an $a$.  You also need to hide the $[n+1,n+1]$ in one of the joints.

There are clearly many more solutions.