Domino Algorithms Revisited

Oct 30, 2025

Back in February, I wrote about applying graph theory to Mexican Train Dominoes. I treated each domino as an edge connecting two nodes (the pip values), and used depth-first search (DFS) to find the “longest train” of dominoes in a hand. That first version worked. Sort of. I first noticed a problem because the "Sort Hand By Longest Sequence" hint button was returning skimpy results. I would see only maybe three or four consecutive dominoes, when I knew there were many more.

In my first approach, I was too focused on using a DFS and an adjacency list. That worked for some hands. With a small hand, the errors of my ways might not even be noticeable. But the DFS approach treated each traversal as isolated. Once a path reached a dead end, it didn’t revisit alternate branches efficiently, and some playable paths were never explored.

I realized this problem is better approached as a backtracking search, which is a type of combinatorial search. Backtracking systematically explores all possible sequences of dominoes, extending chains one domino at a time and pruning paths early when a domino doesn’t fit. This ensures that every valid sequence is considered, unlike the DFS on the adjacency list, which treated each traversal as isolated. Backtracking is conceptually similar to solving the N-Queens problem, generating subsets, or finding Hamiltonian paths. While it is factorial in complexity, the small maximum hand size (around 15 dominoes) makes it computationally manageable in this situation.

I rebuilt the algorithm to explicitly construct every possible chain that can be formed from a given hand. This explores all permutations, but prunes invalid ones early when the next domino doesn’t fit.

The core idea is simple:

  1. Start from each domino in the hand.
  2. Try to extend it by adding any other domino that matches the open end.
  3. Keep going until no more matches exist.
  4. Record each valid chain.

That’s it. Nothing fancy.

Here’s the core function:

function buildAllChains(hand) {
    const allChains = [];

    hand.forEach(startDomino => {
        const stack = [];
        // Each item in stack: { chain: Array of dominoes, usedIds: Set of used domino ids, lastValue: number }
        stack.push({
            chain: [startDomino],
            usedIds: new Set([startDomino.id]),
            lastValue: startDomino.right
        });

        while (stack.length > 0) {
            const { chain, usedIds, lastValue } = stack.pop();

            // Find candidates to extend the chain
            const candidates = hand.filter(domino => {
                if (usedIds.has(domino.id)) return false;
                return domino.left === lastValue || domino.right === lastValue;
            });

            if (candidates.length === 0) {
                // No further extension possible, add chain to allChains
                allChains.push(chain);
            } else {
                candidates.forEach(candidate => {
                    // Orient candidate domino so that left matches lastValue
                    let orientedDomino;
                    if (candidate.left === lastValue) {
                        orientedDomino = candidate;
                    } else {
                        orientedDomino = { ...candidate, left: candidate.right, right: candidate.left };
                    }
                    const newChain = [...chain, orientedDomino];
                    const newUsedIds = new Set(usedIds);
                    newUsedIds.add(candidate.id);
                    stack.push({
                        chain: newChain,
                        usedIds: newUsedIds,
                        lastValue: orientedDomino.right
                    });
                });
            }
        }
    });

    return allChains;
}

This function starts from every domino, explores all the ways to extend it, and collects every valid train it can build. It’s exhaustive but efficient enough for a typical hand (around 15 dominoes).

Once all trains are built, we filter out duplicates (since different traversal paths can lead to the same sequence of domino IDs) and sort them by usefulness. First by length, then by total pip count. Being able to build a long train without the interference of other players and getting rid of high pips first is usually better for game strategy.

const uniqueChainsMap = new Map();
allChains.forEach(chain => {
    const key = chain.map(d => d.id).join(',');
    if (!uniqueChainsMap.has(key)) {
        uniqueChainsMap.set(key, chain);
    }
});
const uniqueChains = Array.from(uniqueChainsMap.values());
const sortedChains = uniqueChains.sort((a, b) => b.length - a.length);

Finally, we take the longest chain, the best train, and reorder the player’s hand so those dominoes are at the front:

const bestChain = sortedChains[0];
const bestChainIds = new Set(bestChain.map(d => d.id));
const remainingDominoes = handCopy.filter(d => !bestChainIds.has(d.id));

const newHand = [...bestChain, ...remainingDominoes];

This produces a reorganized hand where the best playable train is already highlighted and ready for the next move.

The first version of my code was a bit naive. Overall, these sorts of combinatorial search problems are really fun to think about. And I think I found a better way to solve the question of "What is the longest sequence of dominoes I can play right now?" on the second try. You can see it in action, in my Mexican Train Dominoes game built with React-Three-Fiber.

Cassidy Arden