Given 10 domino tiles like below, is it possible to connect them together as a ring?
My idea is to write a graph, starting as a tree with either the tiles with 6 or 3 as root (because there are only 2 tiles for 6 or 3), explore all the possibilities, then see if any leaves can connect back to the root.
However, this seems to be a very expensive brute force approach. Is there a better idea to solve this problem?
Another question about this problem, what properties does a set of domino tiles have in general, if they can be connected as a ring?
Construct a graph with 6 vertices that represent the numbers 1 to 6 that occur on the dominoes. For each domino, draw an edge between the vertices representing the two values on it.
A loop of dominoes corresponds to a loop in the graph. You want to use up all the dominoes, so you want to find a loop that uses all the edges, i.e. an Eulerian circuit of the graph.
It is fairly obvious that for such a circuit to exist you need every vertex to be of even degree (because every number must be used an even number of times) and the graph must be connected (else the dominoes split into two or more sets that do not share any numbers). Less obvious is the reverse: These two properties are also sufficient for the circuit to exist. This is true, and is commonly known as Euler's theorem.