Domino Algorithms Revisited

Oct 30, 2025

Back in February, I wrote about applying graph theory to the algorithms that power my Mexican Train Dominoes web game. The first algorithm version mostly worked, but it became clear something was off. The hint button that was supposed to sort my hand by the longest sequence kept returning very short chains. Only three or four dominoes. When I could clearly see there were longer runs available.

In my first version, I modeled the hand as a graph and used an adjacency list to find sequences with depth-first search. The problem is that the adjacency list represents connectivity between pip values, but it does not represent the fact that each domino can only be used once. DFS on an adjacency list only tells you which moves are possible from a given pip value. It doesn’t track which dominoes have already been used in the current chain. As a result, the algorithm would stop when it reached a dead-end in one traversal, even if a different choice earlier in the chain would have allowed a longer sequence. Basically, it was quitting early.

This problem is fundamentally a combinatorial search over permutations of the dominos, not just a graph traversal problem. A backtracking search is a better approach: at each step, choose a playable domino, place it, mark it as used, and continue. If a path can’t be extended, backtrack and try a different choice. That guarantees every valid ordering is considered, which the adjacency-list-based DFS simply doesn’t do.

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, but it was a great thought exercise. 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