Arranging all the Dominos

Question

Given a Double Twelves Domino Set, prove that the dominos can be arranged in a valid formation such that placement follows the domino placement rules, namely:

• A domino can be placed with the short end touching the short end of another domino, provided that the short end of both dominos match in number of pips.
• A domino with the same number of pips both ends can be placed horizontally perpendicular to another domino, simply for conservation of space, and placing the domino this way does not permit any additional connections.
• A domino can be rotated 90 degrees in either direction to change the direction of the train of dominoes, only for conservation of space.

An image of a Double Twelves Domino Set: it includes, 91 tiles and 1092 pips.

I will accept the best answer, but for extra consideration, provide proof that this works for dominoes going up to size N, or also provide an image of the solution, additional extra consideration will be awarded if the final solution is arranged in a creative, organized shape.

Please use spoilers to hide mathematical proofs, or key answers. Good luck!

Answer 1

The generalization of this problem is already known: https://en.wikipedia.org/wiki/De_Bruijn_sequence. A De Bruijn sequence given an alphabet and a word-length is a string containing, as substrings, all words of that word length with letters from that alphabet exactly once.

We can apply the existing knowledge on De Bruijn sequences (which can be found on the wikipedia page) to this problem. If we set our alphabet to {0, ..., 12} and our word-length to 2, a De Bruijn sequence is exactly a solution to this problem (a word is a domino). There are $\frac{(13!)^{13^1}}{13^2} = 1.25\times10^{125}$ possible solutions for a Double Twelves Domino Set.

There are also algorithms on the wikipedia page that calculate example De Bruijn sequences given alphabet-size and word-length.

EDIT: Note that De Bruijn sequences are cyclic. This is fine however, we can just tack the beginning character onto the end (or beginning $n-1$ characters in the case of word-length $n$).

Answer 2

A double-n set of dominos (for n > 1) can be represented by a graph with n+1 nodes and (n + 1)(n + 2)/2 arcs. The acs represent the individual dominos. A traverse of the graph using each arc exactly once would be equivalent to laying out a domino chain that obeys the rules of dominoes. Inspection of the graph for n = 3 show that no domino chain using all the pieces is possible. This is because the graph has more than two nodes with an odd number of arcs - hence there is no route around it that uses every arc exactly once. In general, whenever n is odd the resultng graph will have more than 2 nodes with an odd number of arcs & hence no domino chain will be possible. When n is even then chains will be possible - for a double-2 set (n=2) there is exaclty one chain and 5 chains that are essentially just rotations or reflections. For a double-4 set there are 132 chains(excluding rotations and reflections). For a double-6 set my computer runs out of memory before completing the count.