Dominoes in Crystal: Complete Solution & Deep Dive Guide

---

Crystal Dominoes: Master the Art of Chaining with Graph Algorithms

Solving the domino chain problem in Crystal involves modeling the dominoes as a graph where numbers are nodes and dominoes are edges. The goal is to find an Eulerian path or circuit, which is a path that visits every edge exactly once, ensuring a continuous and valid chain.

Ever played with a set of dominoes, meticulously lining them up to create that satisfyingly long, unbroken chain? What seems like a simple children's game is actually a fascinating puzzle rooted in deep mathematical principles that have captivated mathematicians for centuries.

In the world of programming, this puzzle transforms into a formidable challenge of logic, data structures, and algorithmic thinking. How do you teach a computer to see the hidden connections in a random jumble of stones and construct the perfect, looping chain? It's a task that can quickly become a tangled mess of nested loops and dead ends if approached without the right strategy.

This comprehensive guide will walk you through solving the domino chaining problem from scratch using the elegant and high-performance Crystal language. We'll demystify the underlying graph theory, build a robust and efficient solution step-by-step, and equip you with the knowledge to conquer this and similar algorithmic challenges. By the end, you'll see dominoes not just as game pieces, but as the edges of a complex graph waiting to be traversed.

---

What Exactly is the Domino Chaining Problem?

Before diving into code, it's crucial to understand the rules of the game. The problem asks us to take a given set of domino stones and arrange them in a sequence, or chain, that adheres to two strict conditions.

First, for any two adjacent dominoes in the chain, the number on the touching halves must be identical. For instance, a [1|2] domino can be followed by a [2|3] domino, but not by a [4|1] domino.

Second, and this is the key constraint that makes the problem interesting, the chain must be circular. This means the number on the first half of the very first domino must match the number on the second half of the very last domino. This creates a closed loop, a perfect circuit.

Consider the set: [1|2], [2|3], and [3|1]. A valid chain would be [1|2] [2|3] [3|1]. Notice how the adjacent halves match (2 with 2, 3 with 3) and the ends also match (the starting 1 with the ending 1). An arrangement like [2|1] [1|3] [3|2] is also perfectly valid. However, if we were given [1|2] and [3|4], no chain is possible.

Why a Simple Loop Isn't Enough

A naive approach might be to try every possible permutation of the dominoes. This is a brute-force method that involves generating all possible orderings and checking if any of them form a valid chain. While this might work for three or four dominoes, the number of permutations grows factorially (n!). For just 10 dominoes, you'd have to check over 3.6 million combinations, making this approach computationally infeasible for even moderately sized sets.

This is where we must look beyond simple iteration and reframe the problem. The solution lies not in permutations, but in connections. This shift in perspective is the gateway to using a powerful mathematical tool: Graph Theory.

---

Why Graph Theory is the Perfect Solution

The domino chaining problem is a classic disguise for a famous problem in graph theory: finding an Eulerian Path or Circuit. By modeling the dominoes as a graph, we unlock a suite of highly efficient algorithms designed specifically for this type of challenge.

Translating Dominoes into a Graph

The translation is surprisingly intuitive. In our graph model:

• Nodes (or Vertices): These are the numbers that can appear on a domino half. Typically, this is the range of numbers from 0 to 6.
• Edges: Each domino stone itself represents an edge. A domino like [2|5] is an undirected edge connecting the node 2 and the node 5.

Let's visualize this with an example set: [1|2], [2|3], [3|1].

      ● Input: Dominoes
      │  [1|2], [2|3], [3|1]
      ▼
    ┌───────────────────┐
    │ Model as a Graph  │
    └─────────┬─────────┘
              │
    ┌─────────┴─────────┐
    │ Nodes = Numbers   │
    │ Edges = Dominoes  │
    └─────────┬─────────┘
              │
              ▼
      (1) ←───[1|2]───→ (2)
       │                 │
     [3|1]             [2|3]
       │                 │
       └──────→ (3) ←─────┘
              │
              ▼
      ● Result: A Connected Graph

Once we have this graph structure, our problem changes. We are no longer asking "How can we order the dominoes?" Instead, we are asking: "Can we find a path in this graph that traverses every single edge exactly once and ends up back where it started?" This is the definition of an Eulerian Circuit.

The Conditions for an Eulerian Circuit

The beauty of graph theory is that it provides clear, simple conditions to check if a solution even exists before we start searching for it. A graph has an Eulerian Circuit if and only if two conditions are met:

1. Connectivity: All vertices with a non-zero degree (i.e., all numbers that actually appear on the dominoes) must belong to a single connected component. In simple terms, you can't have two separate, isolated groups of dominoes.
2. Vertex Degree: Every vertex in the graph must have an even degree. The "degree" of a vertex is the number of edges connected to it. For our dominoes, this means each number must appear on an even number of domino halves.

Why even degrees? Imagine drawing the path. Every time you enter a node through one edge, you must leave it through another. This pairs up the edges connected to that node. The only exceptions are the start and end nodes. Since our problem requires a circuit (the start and end must match), even the start/end node must have its "entry" and "exit" edges paired up. Thus, all nodes must have an even degree.

If the input set is empty, it's a trivial valid chain. If the input has just one domino like [3|3], it's also a valid chain. In all other cases, these two conditions are our gatekeepers. If they aren't met, we can immediately say no solution exists, saving immense computational effort.

---

How to Implement the Domino Chain Solution in Crystal

Now, let's translate this theory into a working Crystal solution. We'll build a class called Dominoes with a primary method, chain, that takes an array of dominoes and returns a valid chain or nil if none exists.

The Complete Crystal Code

Here is the full, commented source code. We will break down each part of it in the following sections.

# A module to solve the domino chaining problem.
# It models the problem as finding an Eulerian circuit in a graph.
module Dominoes
  # Main method to find a valid domino chain.
  # Input is an array of tuples, e.g., [{1, 2}, {2, 3}]
  # Returns an array of tuples representing the chain, or nil if impossible.
  def self.chain(dominoes : Array(Tuple(Int32, Int32))) : Array(Tuple(Int32, Int32))?
    # An empty list of dominoes is a valid, albeit empty, chain.
    return [] of Tuple(Int32, Int32) if dominoes.empty?

    # Build the graph representation (adjacency list) and calculate node degrees.
    graph = build_graph(dominoes)
    degrees = calculate_degrees(graph)

    # Check for the pre-conditions of an Eulerian circuit.
    # 1. All nodes involved must have an even degree.
    # 2. The graph must be connected.
    return nil unless has_eulerian_circuit?(degrees, graph, dominoes)

    # If conditions are met, find the path using Hierholzer's algorithm.
    path = find_eulerian_path(graph, dominoes.first[0])

    # The found path must use all dominoes.
    return nil unless path.size == dominoes.size + 1

    # Convert the node path back into a domino chain.
    reconstruct_chain(path)
  end

  # Builds an adjacency list representation of the graph.
  # A Hash where keys are nodes and values are arrays of neighboring nodes.
  private def self.build_graph(dominoes)
    graph = Hash(Int32, Array(Int32)).new { |h, k| h[k] = [] of Int32 }
    dominoes.each do |a, b|
      graph[a] << b
      graph[b] << a
    end
    graph
  end

  # Calculates the degree of each node in the graph.
  private def self.calculate_degrees(graph)
    degrees = Hash(Int32, Int32).new(0)
    graph.each do |node, neighbors|
      degrees[node] = neighbors.size
    end
    degrees
  end

  # Checks if the graph meets the conditions for an Eulerian circuit.
  private def self.has_eulerian_circuit?(degrees, graph, dominoes)
    # Condition 1: All nodes must have an even degree.
    return false unless degrees.values.all?(&.even?)

    # Condition 2: The graph must be connected.
    # We perform a graph traversal (like DFS) to check this.
    nodes_in_graph = graph.keys
    return true if nodes_in_graph.empty? # Trivial case

    visited = Set(Int32).new
    stack = [nodes_in_graph.first]
    visited.add(nodes_in_graph.first)

    while (current = stack.pop?)
      graph[current].each do |neighbor|
        unless visited.includes?(neighbor)
          visited.add(neighbor)
          stack.push(neighbor)
        end
      end
    end

    # If the set of visited nodes doesn't match all nodes in the graph,
    # it's disconnected.
    visited.size == nodes_in_graph.size
  end

  # Implements Hierholzer's algorithm to find the Eulerian path.
  private def self.find_eulerian_path(graph, start_node)
    # We need a mutable copy of the graph to "remove" edges as we traverse them.
    graph_copy = graph.transform_values(&.clone)
    
    curr_path = [start_node]
    circuit = [] of Int32

    while !curr_path.empty?
      current_node = curr_path.last

      if !graph_copy[current_node].empty?
        # Get the next neighbor and move to it.
        next_node = graph_copy[current_node].pop
        
        # Remove the edge in the other direction as well.
        graph_copy[next_node].delete_one(current_node)

        # Push the new node to our current path stack.
        curr_path.push(next_node)
      else
        # If we are stuck (no more edges), it means we've completed a sub-circuit.
        # Pop from the path and add to the final circuit.
        circuit.push(curr_path.pop)
      end
    end
    
    # The algorithm produces the path in reverse order.
    circuit.reverse
  end

  # Reconstructs the domino chain from the sequence of nodes.
  private def self.reconstruct_chain(path)
    chain = [] of Tuple(Int32, Int32)
    # The path is a list of nodes, e.g., [1, 2, 3, 1].
    # We iterate through pairs to form dominoes: (1,2), (2,3), (3,1).
    path.each_cons(2) do |a, b|
      chain << {a, b}
    end
    chain
  end
end

Step-by-Step Code Walkthrough

1. The Main `chain` Method

This is the public entry point. It orchestrates the entire process:

• It first handles the edge case of an empty input, which is a valid chain.
• It calls build_graph and calculate_degrees to set up our data structures.
• It then acts as a gatekeeper, calling has_eulerian_circuit? to check if a solution is even possible. If not, it returns nil immediately.
• If the checks pass, it proceeds to find the path using find_eulerian_path, which implements the core logic.
• Finally, it validates the path length and uses reconstruct_chain to convert the sequence of nodes back into a list of dominoes.

2. `build_graph` and `calculate_degrees`

These are straightforward helper methods. build_graph creates an adjacency list using a Hash. For a domino {a, b}, it adds b to a's list of neighbors and a to b's list. This represents the undirected edge.

calculate_degrees simply iterates over this graph and counts the number of neighbors for each node, storing it in another Hash for quick lookups.

3. `has_eulerian_circuit?`

This is our crucial validation step. It checks the two core conditions:

• Degree Check: degrees.values.all?(&.even?) is a concise Crystal way to check if every degree value in our hash is an even number.
• Connectivity Check: This is a standard graph traversal. It starts from an arbitrary node, performs a Depth-First Search (DFS) to find all reachable nodes, and stores them in a Set. Finally, it compares the number of visited nodes with the total number of nodes in the graph. If they don't match, the graph is disconnected, and we return false.

4. `find_eulerian_path` (Hierholzer's Algorithm)

This is the heart of our solution. Hierholzer's algorithm is an elegant and efficient method for finding Eulerian circuits. It works like unwinding a ball of yarn.

        ● Start with Graph & Start Node
        │
        ▼
    ┌───────────────────┐
    │ Initialize Stacks │
    │ curr_path = [start]│
    │ circuit = []      │
    └─────────┬─────────┘
              │
        ╭─────▼─────╮
        │ Has Unused│
        │  Edges?   │
        ╰─────◆─────╯
              ╱   ╲
            Yes    No
             │      │
    ┌────────┴───┐  │
    │ Follow Edge│  │
    │ Push to    │  │
    │ curr_path  │  │
    │ Remove Edge│  │
    └────────┬───┘  │
             │      │
             ╰──────╯
                    │
                    ▼
            ┌───────────────┐
            │ Pop from path │
            │ Push to circuit│
            └───────┬───────┘
                    │
            ╭───────▼───────╮
            │ curr_path is  │
            │    Empty?     │
            ╰───────◆───────╯
                  ╱     ╲
                 No     Yes
                  │       │
                  ├───────┘
                  │
                  ▼
            ┌───────────────┐
            │ Reverse circuit│
            │ Return as Path │
            └───────────────┘
                    │
                    ▼
                  ● End

The logic follows these steps:

1. We create a mutable copy of the graph because the algorithm works by consuming edges.
2. We use two stacks (represented as Arrays in Crystal): curr_path to track our current exploration and circuit to build the final result.
3. We start at an arbitrary node (since it's a circuit, any node will do).
4. In the main loop, we look at the node on top of the curr_path stack. If it has any unvisited edges, we pick one, move to the neighbor, "remove" the edge from our graph copy (in both directions), and push the new node onto the curr_path stack.
5. If the current node has no unvisited edges, it means we've hit a dead end. This signifies the completion of a smaller, inner loop. We pop this node from curr_path and push it onto our final circuit array.
6. We continue this process until curr_path is empty. The resulting circuit array, when reversed, gives us the correct sequence of nodes.

---

Where Can This Algorithm Be Applied?

The concept of finding an Eulerian path is far from a mere academic puzzle. It has profound applications in logistics, bioinformatics, and network design.

• Route Planning: Imagine a snowplow that needs to clear every street in a neighborhood exactly once to save fuel and time, or a mail carrier delivering mail to every house on a route. This is a direct application of finding an Eulerian path.
• Network Broadcasting: In computer networks, an efficient algorithm to broadcast a message across every link in a network topology can be modeled as an Eulerian path problem.
• DNA Sequencing: In bioinformatics, assembling a full genome from millions of short, overlapping DNA fragments (reads) is a massive puzzle. Some assembly algorithms model this as finding an Eulerian path in a De Bruijn graph, where DNA sequences are edges.
• Circuit Design: In designing and testing complex integrated circuits (VLSI), algorithms may need to trace every connection on a chip, a task similar to traversing every edge in a graph.

---

Alternative Approaches and Performance

While the Eulerian path approach is optimal, it's worth understanding other ways to think about the problem to appreciate its efficiency.

Brute-Force Backtracking

A brute-force solution would use recursion and backtracking. You would define a function like solve(remaining_dominoes, current_chain). This function would try adding each of the remaining_dominoes to the end of the current_chain if it's a valid move. If it is, it makes a recursive call with the smaller set of dominoes. If that recursive call fails, it "backtracks" by undoing the move and trying the next domino.

This approach is essentially exploring a massive decision tree of all possible permutations. Its time complexity is roughly O(n!), where n is the number of dominoes, making it completely impractical for anything more than a handful of stones.

Pros and Cons: Graph Theory vs. Brute-Force

Aspect	Graph Theory (Eulerian Path)	Brute-Force Backtracking
Performance	Highly efficient. The complexity is O(V + E) or simply O(E) where E is the number of dominoes. It's linear to the input size.	Extremely inefficient. The complexity is factorial, O(n!), making it unusable for non-trivial inputs.
Scalability	Scales very well. Can handle thousands of dominoes with ease.	Does not scale. Becomes too slow with as few as 10-12 dominoes.
Pre-computation	Requires building a graph representation first, which takes a small amount of upfront time and memory.	Requires no pre-computation, it dives straight into searching.
Logic Complexity	Requires understanding graph theory concepts (nodes, edges, degrees, connectivity) and a specific algorithm (Hierholzer's).	The recursive logic can be conceptually simpler for beginners, but it's easy to make mistakes in the state management (passing copies vs. references).
Early Exit	Can determine if a solution is impossible very quickly with degree and connectivity checks before starting the main search.	Will only know a solution is impossible after exhaustively trying every single possibility.

---

Frequently Asked Questions (FAQ)

What happens if the input list of dominoes is empty?

An empty list of dominoes is considered a valid, albeit trivial, chain. Our solution correctly handles this by returning an empty array, as per the problem's requirements often seen in platforms like the kodikra learning path.

How does the code determine that a valid chain is impossible?

The code determines this in two stages. First, it checks if all numbers involved in the domino set appear an even number of times (even degree). Second, it verifies that all dominoes form a single, connected group. If either of these conditions fails, the has_eulerian_circuit? function returns false, and the main method returns nil immediately, without attempting the expensive path-finding logic.

Why do the start and end numbers of the chain have to match?

This requirement is what makes the problem about finding a "circuit" rather than just a "path." An Eulerian path can have two nodes with odd degrees (a start and an end), but an Eulerian circuit requires all nodes to have even degrees, forcing the path to loop back on itself. The problem statement's rule makes it a search for a closed loop.

Is there only one unique solution for a given set of dominoes?

No, often multiple solutions exist. For the set [1|2], [2|3], [3|1], the chain [1|2][2|3][3|1] is valid, but so is [2|3][3|1][1|2] (starting at a different point) and [1|3][3|2][2|1] (reversing the dominoes). Our algorithm will find one of the many possible valid chains.

How does this problem relate to the "Seven Bridges of Königsberg"?

The Seven Bridges of Königsberg is the historical problem that gave birth to graph theory. Leonhard Euler proved in 1736 that it was impossible to walk through the city of Königsberg, crossing each of its seven bridges exactly once. His proof laid the foundation for the concepts of vertex degrees and Eulerian paths. Our domino problem is a modern, structured version of this same fundamental idea.

What makes Crystal a good language for this kind of algorithmic problem?

Crystal shines here for several reasons. Its static type system catches many potential errors at compile time, which is invaluable for complex logic involving data structures like graphs. Its performance, being a compiled language, is on par with languages like C or Go, ensuring the solution is fast. Finally, its Ruby-inspired syntax makes the code clean, readable, and expressive, as seen in the use of blocks and methods like .all? and .each_cons.

---

Conclusion: Beyond the Game

The domino chaining problem is a perfect illustration of a core principle in computer science: finding the right abstraction can transform an impossibly complex problem into a solvable one. By shifting our perspective from a linear sequence of dominoes to a network of nodes and edges, we unlocked a powerful and efficient solution from the field of graph theory.

We've seen how to model the problem, validate the possibility of a solution using the properties of an Eulerian circuit, and implement Hierholzer's algorithm in Crystal to find the chain. This approach is not only elegant but also highly performant, capable of handling vast sets of dominoes where a brute-force method would fail completely.

The skills you've practiced here—data modeling, algorithmic thinking, and understanding trade-offs—are fundamental to software engineering. The next time you see a puzzle, whether it's a game, a logistical challenge, or a data problem, ask yourself: is there a hidden graph waiting to be discovered?

Disclaimer: The solution and code provided in this article are based on Crystal version 1.12.x. While the core logic is timeless, syntax and standard library features may evolve in future versions of the language.

Ready to tackle more algorithmic challenges and deepen your understanding of Crystal? Explore our full Crystal learning path on kodikra.com and continue your journey. For more in-depth tutorials and guides, check out our complete Crystal programming guide.

---

Published by Kodikra — Your trusted Crystal learning resource.