Data Structures & Algorithms for Dominoes

Over the holidays, I played a lot of Mexican Train Dominoes with my family. While drawing tiles and arranging them into sequences, I realized that this game is a surprisingly good application of graph theory.

The dominoes can be interpreted as graph edges. Each domino connects two values, say 6 and 3, which can be thought of as nodes. The dominoes you have in your hand are all the possibilities you have to combine. It can be ideal (depending on your strategy) if you have a long sequence of connecting dominoes in your opening hand, because that guarantees that at least if you can start your sequence with the center double, for a while, you won't have to draw another domino or risk your train becoming open to the entire table.

The challenge, then, is to figure out how many of your tiles can be played in a single sequence where each adjacent domino lines up. This is essentially the problem of finding the longest path in a graph, where each edge can only be used once. I was excited to visualize this computationally, so I wrote a JavaScript function that builds an adjacency list for a hand. Each node is either an "L" or "R" prefixed number to preserve the directionality since some dominoes need to be flipped.

// given a hand of dominoes, create an adjacency list
const playerHand = [
  { id: '1', left: 6, right: 3 },
  { id: '2', left: 3, right: 5 },
  { id: '3', left: 5, right: 2 },
  { id: '4', left: 2, right: 4 },
  { id: '5', left: 6, right: 6 },
  { id: '6', left: 4, right: 1 }
];

function createAdjacencyList(hand) {
  const adjacencyList = {};
  hand.forEach(domino => {
    const keyLeft = `L${domino.left}`;
    const keyRight = `R${domino.right}`;
    if (!adjacencyList[keyLeft]) adjacencyList[keyLeft] = [];
    if (!adjacencyList[keyRight]) adjacencyList[keyRight] = [];
    // each domino's left and right values are recorded,
    // this setup allows the graph to reference a domino from either
    // node value, regardless of order
    adjacencyList[keyLeft].push(domino);
    adjacencyList[keyRight].push(domino);
  });
  return adjacencyList;
}

Once the graph is constructed, I run a depth-first search starting from each domino, building up all possible paths where tiles line up correctly. Each of these paths is called a "train". We recursively explore each path and collect all valid trains.

function dfs(startDomino, adjacencyList, visited) {
    const stack = [[startDomino, [startDomino]]];
    const allTrains = [];

    while (stack.length > 0) {
        const [currentTrain] = stack.pop();
        const trainKeyString = trainKey(currentTrain);

        if (visited.has(trainKeyString)) continue;
        visited.add(trainKeyString);

        allTrains.push(currentTrain);

        const lastValue = currentTrain[currentTrain.length - 1].right;
        const neighbors = adjacencyList[`L${lastValue}`] || [];

        neighbors.forEach(neighbor => {
            if (!currentTrain.some(d => d.id === neighbor.id)) {
                const nextDomino =
                    neighbor.left === lastValue
                        ? neighbor
                        : { ...neighbor, left: neighbor.right, right: neighbor.left };
                        // flips the domino during traversal to use either node value
                stack.push([nextDomino, [...currentTrain, nextDomino]]);
            }
        });
    }

    return allTrains;
}

Once we have a list of all possible trains, we sort them first by length, and then if lengths are tied, by the total number of pips. The assumption here is that longer trains are better, and among them, the train with higher total value might be more strategically useful. Because at the end of the game you have to count your pips, and you want to minimize that number, which means getting rid of the higher value dominoes first.

const sortedTrains = allTrains.sort((a, b) => b.length - a.length);
...
function sumPips(train) {
    return train.reduce((sum, domino) => sum + domino.left + domino.right, 0);
}

longestTrains.sort((a, b) => sumPips(b) - sumPips(a));

Finally, we build a new hand by placing the best train first. This makes it easier for a player or an AI to identify their strongest opening move is without having to calculate everything again later. We can call this function at the start of the game, or whenever we need a hint.

What I liked about this exercise was finding a real world use case for data structures and algorithms. So often we learn these concepts in a vacuum, grinding Leetcode problems for job interviews or cramming for a school exam. And most of the time, we forget them just a few weeks later. But in this case, I was able to apply a depth-first search algorithm and graph data structure to a game I love. It made the experience even more enjoyable, while also making the concepts stick. This algorithm is being used in my multiplayer Mexican Train Dominoes game built with Three.js. I hope to share more about that in the future.