Introduction

Many domino puzzles are really graph problems in disguise. A domino tile such as [2|5] connects the values 2 and 5, so a set of tiles can be treated as a multigraph where values are vertices and tiles are edges.

Once you model the puzzle that way, the matching algorithm becomes much clearer. The main question is whether the tiles can form one continuous chain, and if they can, how to construct it efficiently.

Dominoes as a Graph

Suppose you have these tiles:

[1|2], [2|3], [3|1], [1|4]

Each tile connects two numbers. That is exactly what an edge does in a graph. Double tiles such as [6|6] are simply loops from a vertex back to itself.

This matters because a valid domino chain that uses every tile exactly once is an Eulerian trail:

• Every tile is used once.
• Adjacent tiles share the same number.
• The chain walks through edges, not just vertices.

That means domino chaining is not an arbitrary backtracking puzzle. In the common use all tiles exactly once form, it is a standard graph problem.

When a Full Chain Is Possible

For an undirected graph, an Eulerian trail exists when:

• The graph is connected after ignoring isolated vertices.
• Either zero or two vertices have odd degree.

If zero vertices have odd degree, the chain can start anywhere in the connected component and ends where it started. If two vertices have odd degree, the chain must start at one odd vertex and end at the other.

That maps cleanly to dominoes. Count how many times each pip value appears across tile ends. If more than two values have odd counts, a single full chain is impossible.

Constructing the Chain

The standard algorithm is Hierholzer's algorithm, which builds an Eulerian trail in linear time relative to the number of tiles.

Here is a runnable Python example:

1from collections import defaultdict, Counter
2
3def domino_chain(dominoes):
4    graph = defaultdict(list)
5    degree = Counter()
6
7    for index, (a, b) in enumerate(dominoes):
8        graph[a].append((b, index))
9        graph[b].append((a, index))
10        degree[a] += 1
11        degree[b] += 1
12
13    non_zero = [node for node, deg in degree.items() if deg > 0]
14    if not non_zero:
15        return []
16
17    odd = [node for node, deg in degree.items() if deg % 2 == 1]
18    if len(odd) not in (0, 2):
19        return None
20
21    start = odd[0] if odd else non_zero[0]
22    used = set()
23    stack = [start]
24    path = []
25
26    while stack:
27        node = stack[-1]
28        while graph[node] and graph[node][-1][1] in used:
29            graph[node].pop()
30
31        if not graph[node]:
32            path.append(stack.pop())
33        else:
34            neighbor, edge_id = graph[node].pop()
35            if edge_id not in used:
36                used.add(edge_id)
37                stack.append(neighbor)
38
39    if len(used) != len(dominoes):
40        return None
41
42    return path[::-1]
43
44tiles = [(1, 2), (2, 3), (3, 1), (1, 4)]
45print(domino_chain(tiles))

The returned path is a sequence of values. Consecutive pairs in that path describe the domino order.

Turning the Path Into Tiles

If you want the ordered tiles, reconstruct them from the returned vertex path:

1def path_to_tiles(path):
2    return list(zip(path, path[1:]))
3
4path = domino_chain([(1, 2), (2, 3), (3, 1), (1, 4)])
5print(path_to_tiles(path))

For a multiset of dominoes, there can be multiple valid answers. The algorithm returns one of them, depending on adjacency order.

When Backtracking Is Still Useful

Not every domino problem is exactly an Eulerian trail problem. If the puzzle adds extra rules such as scoring, forbidden placements, board constraints, or use some tiles but maximize length, backtracking or dynamic programming may be needed.

Still, the graph view remains useful because it tells you what structure you are exploring. Many hard-looking domino puzzles become much easier once you first check the degree conditions.

Complexity

For the full-chain version, Hierholzer's algorithm runs in O(E) time, where E is the number of dominoes, assuming adjacency operations are efficient. That is much better than naive brute force, which tries many tile orderings and can become factorial.

This is why graph modeling matters: it turns a brute-force search problem into a direct linear-time construction when the rules match Eulerian traversal.

Common Pitfalls

The biggest mistake is using ordinary pathfinding instead of edge traversal logic. A domino chain uses each tile once, not each pip value once, so vertices can repeat while edges must not.

Another common mistake is forgetting connectivity. Even if the odd-degree rule passes, a disconnected set of tiles still cannot form one full chain.

Double tiles such as [4|4] also confuse implementations. They contribute two to the degree of vertex 4, not one.

Finally, if the task is not use every tile exactly once, do not force an Eulerian solution onto it. Some domino optimization problems need a different algorithm entirely.

Summary

• A domino set can be modeled as an undirected multigraph.
• A full chain using every tile exactly once is an Eulerian trail problem.
• The chain exists only when the graph is connected and has zero or two odd-degree vertices.
• Hierholzer's algorithm builds a valid chain in linear time.
• Extra puzzle rules can turn the problem into backtracking or optimization rather than pure graph traversal.