---

From Zero to Hero: Mastering Recursive Domino Chains in Clojure

Discover how to solve the classic domino chaining puzzle using Clojure's powerful functional programming capabilities. This guide breaks down the recursive logic, provides a detailed code walkthrough, and explores the elegant patterns that make Clojure ideal for complex combinatorial problems.

---

Imagine a child's playroom, floor scattered with colorful dominoes. The goal isn't just to topple them, but to arrange them into a perfect, continuous, closed loop where every piece connects seamlessly. You pick up a piece, say a [2|5], and search for a domino with a 2 or a 5. You find a [5|1], a perfect match! But now you need a 1, and the remaining pieces are [4|6] and [3|4]. It's a dead end. You backtrack, sigh, and start over. This frustrating trial-and-error is a classic computer science problem in disguise.

If you've ever felt stuck on a problem that involves permutations, paths, or exploring possibilities, you're in the right place. This challenge isn't just about dominoes; it's about learning a fundamental recursive backtracking strategy. In this deep dive, we'll transform that manual frustration into an elegant, automated solution using Clojure, a language practically built for this kind of thinking. We will dissect a solution from the exclusive kodikra.com Clojure curriculum, turning abstract logic into concrete, functional code.

---

What Exactly is the Domino Chaining Problem?

Before we write a single line of code, it's crucial to have a crystal-clear understanding of the rules. The problem provides a set of dominoes, where each domino is represented as a pair of numbers, like [1 2].

The objective is to determine if these dominoes can be arranged in a sequence to form a valid, closed chain. A valid chain has two strict rules:

1. Adjacency Rule: The touching halves of any two adjacent dominoes must have the same number. For example, [1 2] can be followed by [2 3], but not by [4 5].
2. Closure Rule: The chain must form a loop. 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.

For instance, given the set [[1 2] [2 3] [3 1]], a valid chain is [1 2] [2 3] [3 1]. The first number (1) matches the last number (1), and all internal numbers match up correctly. An input of [[1 2] [4 1] [2 3]] cannot form a valid chain because there's no way to connect the 3 and the 4.

Our function's goal is not to return the chain itself, but to simply answer the question: "Is a valid, closed chain possible?" with a boolean true or false.

---

Why is Clojure the Perfect Tool for This Puzzle?

While you could solve this problem in any language, Clojure's design philosophy and feature set make it exceptionally well-suited for this kind of recursive, data-transformation task. Its functional nature provides a clearer, more robust way to handle the logic.

Immutability and Purity

In Clojure, data structures are immutable by default. When we "remove" a domino from our set to use it in the chain, we aren't modifying the original list. Instead, we generate a *new* list without that domino. This prevents a whole class of bugs related to state management. Our recursive function can operate on data without causing side effects, making the logic easier to reason about and test.

Powerful Sequence Abstractions

Clojure treats almost everything as a sequence, and it provides a rich library of functions to manipulate them. Functions like for, map, filter, reduce, and some are the building blocks of idiomatic Clojure. For the domino problem, we can use a list comprehension (for) to elegantly generate all possible next steps from a given state, which is far more concise than traditional loops with conditional breaks.

First-Class Functions and Recursion

Recursion is the natural way to express the "try a piece, then solve the rest of the puzzle" logic. In Clojure, functions are first-class citizens, meaning they can be passed as arguments to other functions. This allows for powerful patterns, like using the some function to find the *first* successful recursive path without needing to explore all of them, leading to a more efficient search.

Destructuring

Destructuring is a feature that lets you bind names to the inner parts of a data structure directly. Instead of accessing elements by index like (get my-vector 0), you can write [a b] to immediately get the first and second elements. This makes the code for handling domino pairs (e.g., [head & tail]) incredibly clean and readable.

---

How to Approach the Solution: A Recursive Backtracking Strategy

The core of the problem is a search. We need to search through the space of all possible domino arrangements to see if any of them form a valid chain. A brute-force approach would be to generate every single permutation of the dominoes and check each one, but that's wildly inefficient.

A much smarter approach is recursive backtracking. Think of it as building the chain one piece at a time and abandoning a path as soon as it's clear it won't work.

Here is the high-level algorithm:

1. Start Somewhere: Pick the first domino from the list, say [a b]. This is our starting point. The number a is our "starting peg," and the number b is the number we now need to match. The remaining dominoes form our pool of available pieces.
2. Find a Match: Look through the pool of available dominoes. Can you find one that has the number b on either of its halves?
3. Explore the Path:
   • If you find a match (e.g., [b c]), this is a promising path. Now, the problem is smaller: you need to form a chain from the *remaining* pool of dominoes that starts with c and eventually ends with our original "starting peg" a. You recursively call your function with this new, smaller problem.
   • If you find a match but it's flipped (e.g., [c b]), that's also fine! You use it as [b c], and now you recursively search for a chain starting with c.
4. Backtrack on Dead Ends: If you search the entire pool and find no domino with the number b, this path is a dead end. You must "backtrack" and try a different choice at a previous step. In our recursive model, this simply means a recursive call returns a "failure" signal (like nil or false).
5. Base Case (Success): The recursion stops when the pool of available dominoes is empty. If you've successfully used all the dominoes, you just need to check one last thing: does the last number you needed to match (say, z) equal your original "starting peg" a? If yes, you've found a valid closed chain! You return a "success" signal.

This recursive exploration of possibilities can be visualized as a tree search.

● Start with [1|2] and pool {[2|3], [3|1]}
│
└─ Need to match '2'
   │
   ▼
┌───────────────────┐
│ Find [2|3] in pool│
└─────────┬─────────┘
          │
          ├─ New Goal: Match '3' with pool {[3|1]}
          │
          ▼
       ┌───────────────────┐
       │ Find [3|1] in pool│
       └─────────┬─────────┘
                 │
                 ├─ New Goal: Match '1' with empty pool {}
                 │
                 ▼
              ◆ Is pool empty? (Yes)
              │
              └─ ◆ Does final number '1' == start '1'? (Yes)
                 │
                 ▼
              ✅ Success!

The beauty of this approach is that we stop exploring a branch of the search tree the moment it fails, which can save a massive amount of computation.

---

The Complete Clojure Solution: A Detailed Code Walkthrough

Now let's dive into the idiomatic Clojure code that implements this strategy. The solution is broken down into a few helper functions that compose together beautifully.

(ns dominoes)

(defn next-stones
  "Finds all possible next stones from a set 'ds' that can connect to number 'n'.
  Returns a sequence of [next-number remaining-stones] pairs."
  [n ds]
  (for [i (range (count ds))
        :let [[l [[a b] & r]] (split-at i ds)
              m (cond (= a n) b
                      (= b n) a)]
        :when m]
    [m (concat l r)]))

(defn chain-end
  "Recursively tries to complete a chain starting with number 'b' and stones 'ds'."
  [b ds]
  (some (fn [[next-b remaining-ds]]
          (if (empty? remaining-ds)
            next-b
            (chain-end next-b remaining-ds)))
        (next-stones b ds)))

(defn can-chain?
  "Checks if a given collection of dominoes can form a valid closed chain."
  [dominoes]
  (if (empty? dominoes)
    true
    (let [[[a b] & ds] dominoes]
      (if (empty? ds)
        (= a b)
        (= a (chain-end b (vec ds)))))))

Part 1: next-stones - Finding the Next Move

This function is the workhorse of our search. Its job is to answer the question: "Given the number I need to match (n) and a collection of available dominoes (ds), what are all the possible next moves I can make?"

A "move" is defined as a pair containing the *new* number to match and the *remaining* pool of dominoes.

(defn next-stones [n ds]
  (for [i (range (count ds))
        :let [[l [[a b] & r]] (split-at i ds)
              m (cond (= a n) b
                      (= b n) a)]
        :when m]
    [m (concat l r)]))

Let's break down the powerful for list comprehension line by line:

• (for [i (range (count ds)) ...]): This sets up a loop that iterates through the *indices* of the dominoes vector ds. We iterate by index because it's a clever way to select each domino one by one while also easily reconstructing the list of remaining dominoes.
• :let [[l [[a b] & r]] (split-at i ds) ...]: This is the most complex part.
  • (split-at i ds) splits the vector ds into two parts at index i. For example, if ds is [[1 2] [3 4] [5 6]] and i is 1, it returns [[[1 2]] [[3 4] [5 6]]].
  • We then destructure this result. l gets bound to the first part (the dominoes *before* the one we picked), e.g., [[1 2]].
  • The second part is destructured further: [[a b] & r]. [a b] gets bound to the first element of the second part (the domino we're currently inspecting), e.g., [3 4]. r gets bound to the rest of the second part, e.g., [[5 6]].
• m (cond (= a n) b (= b n) a)]: This is the matching logic. It checks if either half of the current domino [a b] matches our target number n. If a matches n, then m becomes b (the other half). If b matches n, then m becomes a. If neither matches, m becomes nil.
• :when m: This is a filter. The loop only proceeds for the current domino if m is not nil. In other words, it only continues if we found a valid match.
• [m (concat l r)]: This is the value produced by the comprehension for each successful match. It's a vector containing the new number to match (m) and the remaining dominoes, which are reconstructed by concatenating the parts before our chosen domino (l) and the parts after it (r).

This function's data flow is a great example of functional data transformation.

● Input: n=2, ds=[[4|1], [2|5], [5|3]]
│
├─ Loop 1 (i=0): domino=[4|1]
│  │
│  └─ No match for n=2. Skip.
│
├─ Loop 2 (i=1): domino=[2|5]
│  │
│  ├─ Match found! n=2 equals 'a'.
│  │  m becomes '5'.
│  │  Remaining stones = [4|1] ++ [5|3]
│  │
│  └─⟶ Yield: [5, [[4|1], [5|3]]]
│
└─ Loop 3 (i=2): domino=[5|3]
   │
   └─ No match for n=2. Skip.

      │
      ▼
● Final Output: ([5, [[4|1], [5|3]]])

Part 2: chain-end - The Recursive Engine

This function performs the recursive search. It takes the number we need to match (b) and the available dominoes (ds) and tries to find a way to use them all up.

(defn chain-end [b ds]
  (some (fn [[next-b remaining-ds]]
          (if (empty? remaining-ds)
            next-b
            (chain-end next-b remaining-ds)))
        (next-stones b ds)))

• (next-stones b ds): First, it calls our helper to get all possible next moves. This might return an empty sequence (if no moves are possible) or a sequence of moves like ([5, [[4 1]]] [3, [[6 2]]]).
• (some (fn [...] ...)): some is a key function here. It applies an anonymous function to each item in a sequence and returns the *first logical true* (i.e., not nil or false) result it finds. This is perfect for our search; we only need to find *one* valid chain, not all of them. As soon as a recursive path returns a successful result, some stops and returns that result immediately.
• (fn [[next-b remaining-ds]] ...): This is the function applied to each possible move generated by next-stones. It destructures the move into the new target number next-b and the new pool remaining-ds.
• (if (empty? remaining-ds) next-b ...): This is our base case. If we've successfully used up all the dominoes, we return the final number (next-b). This final number will be checked against the very first number in the main function.
• (chain-end next-b remaining-ds): This is the recursive step. If there are still dominoes left, we call chain-end again with the new state. The result of this recursive call will propagate back up. If it eventually finds a solution, it will return the final number; if it hits a dead end, it will return nil.

Part 3: can-chain? - The Entry Point

This is the main function that ties everything together. It sets up the initial problem and interprets the final result.

(defn can-chain? [dominoes]
  (if (empty? dominoes)
    true
    (let [[[a b] & ds] dominoes]
      (if (empty? ds)
        (= a b)
        (= a (chain-end b (vec ds)))))))

• (if (empty? dominoes) true ...): It handles the edge case of an empty input. An empty set of dominoes technically forms a valid (empty) chain.
• (let [[[a b] & ds] dominoes] ...): It destructures the input list. [a b] becomes the first domino, and ds becomes a sequence of all the rest. a is our "starting peg" that the chain must ultimately connect back to. b is the first number we need to match.
• (if (empty? ds) (= a b) ...): It handles the edge case of a single domino. A chain of one is only valid if it's a double, like [6 6], because the start and end must match.
• (= a (chain-end b (vec ds))): This is the final, elegant expression of our goal. It calls our recursive engine chain-end with the initial state (match number b using the pool ds).
  • If chain-end successfully finds a path, it will return the final number of the chain. We then check if this final number is equal to our starting number a. If they match, the whole expression is true.
  • If chain-end fails to find a path, it returns nil. The expression (= a nil) will be false (unless a was somehow nil, which it won't be), correctly indicating failure.
• (vec ds): We convert the remaining dominoes to a vector because our split-at logic in next-stones is most efficient and idiomatic with indexed collections like vectors.

---

Pros and Cons of This Recursive Approach

Every algorithm has trade-offs. While this solution is functionally pure and elegant, it's important to understand its strengths and weaknesses.

Pros	Cons / Risks
Highly Declarative: The code reads like a description of the problem's logic rather than a set of low-level, step-by-step instructions.	Performance: For large sets of dominoes with many possible connections, the number of recursive paths can grow exponentially (O(n!)), leading to slow performance.
Immutability & Safety: By never modifying data structures in place, the code is free from side-effect bugs and is inherently thread-safe.	Stack Overflow Risk: Standard recursion in Clojure is not tail-call optimized by default. A very long chain could theoretically exceed the JVM's call stack limit, though this is unlikely for typical problem constraints.
Concise and Idiomatic: The use of for, some, and destructuring is classic Clojure, making it easy to understand for experienced developers in the ecosystem.	Conceptual Complexity: The logic, especially the destructuring inside the for comprehension, can be dense and challenging for programmers new to functional programming or Clojure's specific idioms.
Correctness: The backtracking approach correctly explores the entire problem space, guaranteeing it will find a solution if one exists.	Graph Theory Equivalence: This problem is equivalent to finding an Eulerian circuit in a graph. Specialized graph algorithms (like Hierholzer's algorithm) are more efficient for very large inputs but are also more complex to implement.

---

Frequently Asked Questions (FAQ)

What happens if the input is an empty list of dominoes?

The can-chain? function handles this as the first condition. An empty list is considered a valid chain, and the function correctly returns true. This is a logical convention for such problems.

Is the order of the output chain important?

For this specific problem from the kodikra learning path, no. The goal is only to determine if a valid chain is *possible*. The function returns a boolean true or false, not the chain itself. Modifying the code to return the actual chain would involve accumulating the path during the recursion.

How does the code handle "double" dominoes like [6 6]?

The matching logic (cond (= a n) b (= b n) a) handles doubles perfectly. If we are looking for a 6 and encounter [6 6], the first condition (= a n) will be true, and the next number to match will be b, which is also 6. The logic remains sound.

Why use some instead of a different looping construct?

some is used for its short-circuiting behavior. It stops processing and returns as soon as it finds the first "truthy" value. In a search problem, this is highly efficient. Once we find one valid path, we don't need to waste time exploring any other alternative paths. A map or for would needlessly continue searching all possibilities.

Is this solution tail-recursive?

No, it is not. A function is tail-recursive if the recursive call is the very last operation. In chain-end, the recursive call is (chain-end next-b remaining-ds), which is inside an anonymous function passed to some. The result of the recursion is used by some, so it's not in a tail position. For deep recursion, one might need to refactor this using a loop/recur construct to achieve tail-call optimization (TCO) in Clojure.

What is the time complexity of this algorithm?

In the worst-case scenario, where many connections are possible at each step, the algorithm may have to explore a large number of permutations. The time complexity is roughly proportional to the number of possible chains, which can be factorial in nature, approaching O(n!), where n is the number of dominoes. This makes it suitable for small to medium-sized inputs but not for extremely large sets.

Could this problem be solved with a different approach in Clojure, like using graphs?

Absolutely. A more advanced approach would be to model the problem as a graph. Each number (0-6) can be a node in the graph. Each domino [a b] represents an edge between node a and node b. The problem then becomes finding an Eulerian circuit in this graph—a path that visits every edge exactly once and ends where it started. This requires checking if all vertices have an even degree (number of connections), which can be much faster for large inputs.

---

Conclusion: The Elegance of Functional Problem-Solving

We've journeyed from a simple playroom puzzle to a deep, functional implementation in Clojure. The domino chaining problem serves as a perfect example of how recursive backtracking can elegantly solve complex combinatorial challenges. By leveraging Clojure's core strengths—immutability, powerful sequence functions, and a recursive mindset—we built a solution that is not only correct but also concise and declarative.

The key takeaways are the power of breaking a large problem into smaller, self-similar subproblems and using functions like some to efficiently search for the first valid solution. While the performance has its limits, the clarity and safety of this functional approach are immense assets for building robust software.

This challenge is a fantastic stepping stone. If you enjoyed this deep dive, consider continuing your journey through the Kodikra Clojure Module 7 roadmap or explore our comprehensive guides to master the full Clojure language and its powerful ecosystem.

Disclaimer: All code examples are written for modern Clojure versions (1.10+). The core logic and functions used are fundamental and stable across recent releases.

---

Published by Kodikra — Your trusted Clojure learning resource.