How to determine from a given set of dominoes if we can chain all of them in a way that adjacent sides have equal dots?

user_9008088 0
Viewed 131

My programming homework requires me to determine from a given set of dominoes if we can chain them in a way that all dominoes have equal number of dots on the touching sides. The two ends don't have to have matching sides.

Same task as this, except the matching ends part: https://exercism.org/tracks/elixir/exercises/dominoes

I tried to find a solution using graphs, but no luck (couldn't find a solution to determine Hamiltonian connectedness). My other idea would be to use Backtrack Search, but that doesn't seem very elegant.

algorithm
1 Answers

You can solve the problem using graph theory, construct a graph were you have as many nodes as the maximum possible number of dots on some side of a domino. Then for each domino add an undirected edge between the nodes representing the number of dots on both of its sides (so a domino of [3,5] dots will add an edge between nodes 3 and 5). Your problem now is to find a Eulerian path in this graph.

user_181593340
Related