Cairo Dominoes: The Complete Guide to Building Chains with Graph Theory

Discover how to solve the classic domino chaining problem using the Cairo programming language. This guide breaks down the logic, from graph theory concepts to a detailed, line-by-line code implementation using a recursive backtracking algorithm, perfect for mastering complex problem-solving in Cairo.

The Puzzle of the Toyland Express

Imagine a bustling city built entirely of toys, where the primary mode of transport is a network of miniature trains. These trains don't run on ordinary steel tracks; instead, they traverse colorful paths made of dominoes. For the Toyland Express to deliver its precious cargo—from sparkling marbles to the latest building blocks—the domino track must form a perfect, continuous loop.

Today, a critical shipment is stalled. You, as the chief engineer, have been handed a jumbled box of domino track pieces. The train can only depart if you can prove that these pieces can form a valid, unbroken chain. The rule is simple: the number of dots on one half of a domino must exactly match the number on the adjacent half of the next. Furthermore, to create a perfect loop for the train, the number on the very first domino's open end must match the number on the very last one.

This isn't just a child's game; it's a fascinating algorithmic puzzle that tests your logical thinking and programming skills. In this guide, we will embark on a journey to solve this very problem using the power and unique features of Cairo, turning a chaotic pile of dominoes into an elegant, functional chain. You will learn not just the solution, but the fundamental computer science principles that underpin it.

What is the Domino Chaining Problem?

At its core, the Domino Chaining Problem is a combinatorial puzzle. Given a set of dominoes, the objective is to determine if they can be arranged in a sequence such that adjacent dominoes have matching numbers on their touching halves. A special condition for a "perfect chain" is that the sequence must be circular, meaning the first and last numbers in the chain are also identical.

For instance, if you are given the dominoes [1|2], [2|3], and [3|1], a valid chain would be [1|2] [2|3] [3|1]. Notice how the inner numbers match (2 with 2, 3 with 3) and the outer numbers also match (1 with 1), forming a closed loop.

This problem might seem simple with three dominoes, but it becomes exponentially more complex as the number of dominoes increases. A brute-force approach, trying every possible permutation, is computationally infeasible. This is where a more intelligent strategy is required, one rooted in the elegant world of graph theory.

Why Graph Theory is the Perfect Model

The most effective way to visualize and solve this problem is to reframe it as a graph traversal challenge. In this model:

• Nodes (Vertices): The numbers on the domino halves (e.g., 1, 2, 3, 4, 5, 6) become the nodes of our graph.
• Edges: Each domino itself, like [2|3], represents an edge connecting the two corresponding nodes (an edge between node 2 and node 3).

When we frame the problem this way, our goal transforms. We are no longer just arranging dominoes; we are searching for a specific type of path within a graph. The challenge is to find a path that visits every single edge (domino) exactly once, starting and ending at the same node. In graph theory, this is known as finding an Eulerian Circuit.

An Eulerian circuit exists in a graph if and only if two conditions are met:

1. The graph is connected (ignoring isolated nodes with no dominoes).
2. Every node in the graph has an even "degree" (the number of edges connected to it).

Thinking in these terms provides a powerful mental framework and guides our algorithmic approach. We will use a technique called backtracking search, a form of Depth-First Search (DFS), to explore the possible paths in this graph.

    ● Start with dominoes: [1|2], [2|3], [3|1]
    │
    ▼
  ┌───────────────────────────────┐
  │ Convert to Graph Representation │
  └───────────────┬───────────────┘
                  │
                  ▼
      (1) ─────── (2) ─────── (3)
       \           /           /
        \         /           /
         \       /           /
      [1|2] Edge  [2|3] Edge  [3|1] Edge connects (3) back to (1)
           \     /
            \   /
             \ /
    ┌─────────┴─────────┐
    │ Find a path that  │
    │ uses every edge   │
    │ exactly once and  │
    │ returns to start. │
    └─────────┬─────────┘
              │
              ▼
           ● Solution: A valid Eulerian Circuit (the chain).

How to Implement the Domino Chainer in Cairo

To solve this in Cairo, we need to design data structures to represent our dominoes and the state of our search, and then build a recursive function that explores the graph. Our strategy will be to pick a starting domino, add it to our chain, and then recursively try to find the next valid domino from the remaining pool until we either complete the chain or hit a dead end.

Key Data Structures

First, let's define the core components of our solution. We'll need a way to represent a single domino and a way to keep track of which dominoes are still available to be placed in the chain.

1. The `Domino` Type

A domino is simply a pair of numbers. In Cairo, a tuple is a perfect and efficient way to represent this. We'll define a type alias for clarity.

pub type Domino = (u8, u8);

2. The `AvailabilityTable` Struct

This is the most critical data structure. We need an efficient way to check which dominoes are available and to "use" one up during our recursive search. The solution from the kodikra learning path uses a clever approach with a Felt252Dict, which acts like a hash map.

This table essentially represents the adjacency matrix of our graph. It tracks the count of each type of domino. For a domino like [2|3], it's the same as [3|2], so we need a consistent way to store and retrieve it. A helper function, index(x, y), will create a unique key for each domino pair, ensuring that index(2, 3) and index(3, 2) produce the same key.

#[derive(Destruct)]
struct AvailabilityTable {
    d: Felt252Dict<u8>,
    len: usize,
}

// Helper to create a consistent key for a domino pair.
// Ensures that (x, y) and (y, x) map to the same index.
fn index(x: u8, y: u8) -> u8 {
    if x <= y {
        (x - 1) * 6 + y
    } else {
        (y - 1) * 6 + x
    }
}

The AvailabilityTable stores a dictionary `d` mapping the unique index to the count of that domino, and a `len` field to track the total number of dominoes remaining.

The Backtracking Algorithm Logic

Our core logic resides in a recursive function, let's call it `can_chain_recursive`. This function will try to build the chain step-by-step.

Here’s the high-level process:

1. Base Case: If we have used all the dominoes (the length of our chain equals the original number of dominoes), we just need to check one final thing: does the end of our chain match the beginning? If yes, we've found a valid circular chain! We return `true`.
2. Recursive Step:
   • Look at the last number of the current chain. Let's call it `current_val`.
   • Iterate through all possible next numbers (1 through 6).
   • For each potential next number, `next_val`, check the `AvailabilityTable` to see if a domino `[current_val|next_val]` exists.
   • If it exists:
     1. "Take" the domino from the table (decrement its count).
     2. Add the new domino to our `chain`.
     3. Make a recursive call to `can_chain_recursive` with the updated state.
     4. If the recursive call returns `true`, it means a solution was found down that path. We can stop and propagate `true` all the way up.
     5. Backtrack: If the recursive call returns `false`, it means this path was a dead end. We must undo our choice. We "put back" the domino into the table (increment its count) and remove it from our `chain`. Then, we continue our loop to try the next possible domino.
3. Failure: If we iterate through all possible next dominoes and none of them lead to a solution, we return `false` from the current recursive call, signaling to the previous call that this path failed.

Where the Magic Happens: A Detailed Code Walkthrough

Now, let's dive deep into the Cairo code from the kodikra.com module. We will analyze each function to understand its role in the overall solution. For a complete learning experience, you can explore the full Cairo learning path on kodikra.com.

The `AvailabilityTable` Implementation

This struct manages the pool of available dominoes. Let's look at its methods.

impl AvailabilityTableImpl of AvailabilityTableTrait {
    // Creates a new table from an input slice of dominoes.
    fn new(input: @Array<Domino>) -> AvailabilityTable {
        let mut d = Felt252DictTrait::new();
        let mut i = 0;
        let len = input.len();
        loop {
            if i == len {
                break;
            }
            let domino = input.at(i);
            let (x, y) = *domino;
            let idx = index(x, y);
            // Increment the count for this domino type.
            d.insert(idx.into(), d.get(idx.into()) + 1);
            i += 1;
        };
        AvailabilityTable { d, len }
    }

    // Returns the number of dominoes remaining.
    fn len(self: @AvailabilityTable) -> usize {
        *self.len
    }

    // "Takes" a domino from the table, reducing its count.
    // Returns true on success, false if the domino isn't available.
    fn take(ref self: AvailabilityTable, x: u8, y: u8) -> bool {
        let idx = index(x, y);
        let count = self.d.get(idx.into());
        if count == 0 {
            return false;
        }
        self.d.insert(idx.into(), count - 1);
        self.len -= 1;
        true
    }

    // "Puts back" a domino, restoring its count. Used for backtracking.
    fn put_back(ref self: AvailabilityTable, x: u8, y: u8) {
        let idx = index(x, y);
        self.d.insert(idx.into(), self.d.get(idx.into()) + 1);
        self.len += 1;
    }
}

• new(): This constructor initializes the table. It iterates through the input array of dominoes. For each domino (x, y), it calculates the canonical index and increments the count for that index in the dictionary d.
• len(): A simple getter that returns the total number of dominoes left to be placed.
• take(x, y): This is the action of using a domino. It finds the index for the pair (x, y), checks if its count in the dictionary is greater than zero. If it is, it decrements the count and the total length, then returns true. If the count is already zero, it returns false.
• put_back(x, y): This is the undo operation for backtracking. It simply increments the count for the given domino, effectively making it available again.

The Recursive Core: `can_chain_recursive`

This is the heart of the algorithm. It performs the depth-first search to find a valid chain.

fn can_chain_recursive(
    ref table: AvailabilityTable, mut chain: Array<Domino>, first_val: u8
) -> Option<Array<Domino>> {
    // Base Case: Have we used all dominoes?
    if table.len() == 0 {
        let (last_x, last_y) = *chain.at(chain.len() - 1);
        // Check if the chain forms a circle.
        if last_y == first_val {
            return Option::Some(chain);
        } else {
            return Option::None;
        }
    }

    let (prev_x, prev_y) = *chain.at(chain.len() - 1);
    let mut next_val: u8 = 1;
    loop {
        // Loop through all possible next values (1 to 6).
        if next_val > 6 {
            break;
        }

        // Try to find a domino that connects prev_y to next_val.
        if table.take(prev_y, next_val) {
            // If found, add it to the chain.
            chain.append((prev_y, next_val));
            // Make the recursive call.
            let result = can_chain_recursive(ref table, chain, first_val);

            // Check if the recursive call found a solution.
            if result.is_some() {
                return result; // Success! Propagate the solution up.
            }

            // Backtrack: The path failed. Undo the move.
            chain = result.unwrap_err(); // Retrieve the chain from the failed Option
            chain.pop_front(); // This is a trick to get the array back from Option::None
            table.put_back(prev_y, next_val);
        }
        next_val += 1;
    };

    // If the loop finishes without finding a solution, this path is a dead end.
    Option::None
}

Let's break down this complex function:

1. Parameters: It takes the mutable table, the current chain being built, and the first_val from the very first domino to check for the circular condition at the end.
2. Base Case: When table.len() == 0, all dominoes have been placed. It then checks if the second number of the last domino (last_y) matches the first number of the first domino (first_val). If they match, it returns Some(chain), signaling success. Otherwise, None.
3. Recursive Step:
   • It gets the last domino added to the chain to know which number to match (prev_y).
   • It loops next_val from 1 to 6.
   • Inside the loop, it calls table.take(prev_y, next_val). This is the key move: it attempts to find and use a domino that connects the end of our current chain to a new number.
   • If take() succeeds, it appends the new domino and makes the recursive call.
   • Crucially, if that recursive call returns Some(result), it means the rest of the chain was successfully built from that point. The function immediately returns this successful result.
   • If the call returns None, it means the choice was wrong. The code then backtracks by calling table.put_back(...) and removing the last added domino (the chain.pop_front() after unwrapping the error is a Cairo-specific pattern to manage memory and ownership of the array).
4. Failure: If the loop from 1 to 6 completes without any path returning a successful result, it means there's no way to continue from the current chain state. The function returns None.

The Public Interface: `can_chain`

This function is the entry point for the user. It handles the initial setup and edge cases before kicking off the recursion.

pub fn can_chain(dominoes: @Array<Domino>) -> Option<Array<Domino>> {
    if dominoes.len() == 0 {
        return Option::Some(ArrayTrait::new());
    }

    let mut table = AvailabilityTableImpl::new(dominoes);
    let mut chain = ArrayTrait::new();

    // Start the chain with the first domino from the input.
    let (first_x, first_y) = *dominoes.at(0);
    table.take(first_x, first_y);
    chain.append((first_x, first_y));

    // Kick off the recursive search.
    let result = can_chain_recursive(ref table, chain, first_x);

    if result.is_some() {
        return result;
    }

    // If the first orientation [x, y] failed, try the other one [y, x].
    // This is necessary if the first domino is not a double.
    if first_x != first_y {
        // Reset the state
        table.put_back(first_x, first_y);
        let mut chain = result.unwrap_err(); // Get the chain back
        chain.pop_front(); // Clear the chain

        // Try starting with the domino flipped
        table.take(first_y, first_x);
        chain.append((first_y, first_x));
        return can_chain_recursive(ref table, chain, first_y);
    }

    Option::None
}

This function handles a few important details:

• Empty Input: If the input array of dominoes is empty, it correctly returns an empty chain as a valid solution.
• Initialization: It creates the AvailabilityTable and the initial chain array.
• First Move: It takes the first domino from the input list to "anchor" the search. This is a crucial starting point. It adds this domino to the chain and removes it from the table.
• Starting Recursion: It calls can_chain_recursive with this initial state.
• Handling Orientation: If the first attempt fails, and the starting domino is not a double (e.g., it's [1|2], not [1|1]), the algorithm might have failed because it started with the wrong orientation. The code backtracks completely, resets the state, and tries again, but this time starting with the first domino flipped (e.g., starting with [2|1] instead of [1|2]). This ensures all possibilities are covered.

When Does This Solution Succeed or Fail?

The backtracking algorithm is powerful but has its limitations and specific conditions under which it operates. Understanding these helps in debugging and appreciating the complexity of the problem.

Conditions for Success

The algorithm will successfully find a chain if an Eulerian circuit exists in the graph representation of the dominoes. This generally means:

• All dominoes form a single connected component. If you have two separate sets of dominoes that cannot be linked (e.g., [1|2], [2|1] and [4|5], [5|4]), you cannot form a single chain.
• The "degree" of each number (node) is even. The degree is the total count of times a number appears across all dominoes. For example, in [1|2], [2|3], [3|1], the number '1' appears twice, '2' appears twice, and '3' appears twice. All degrees are even, so a circuit is possible. If you had [1|2], [2|3], the degree of '1' is one and '3' is one (odd), so a circular chain is impossible.

Potential Pitfalls and Edge Cases

A Step-by-Step Example Walkthrough

Let's trace the execution with a simple input: `dominoes = [(1, 2), (2, 3), (3, 1)]`.

1. Initialization in `can_chain`:**

• table is created with counts: `index(1,2): 1`, `index(2,3): 1`, `index(1,3): 1`. `len = 3`.
• First domino `(1, 2)` is chosen as the start.
• table.take(1, 2)` is called. `table.len` becomes 2.
• chain` is now `[(1, 2)]`.
• `can_chain_recursive` is called with `chain = [(1, 2)]` and `first_val = 1`.

    ● `can_chain([(1,2), (2,3), (3,1)])`
    │
    ├─ Start with (1,2). `chain`=[(1,2)], `first`=1
    │
    ▼
  ┌─────────────────────────────────────────┐
  │ `recursive(chain=[(1,2)], first=1)`     │
  │  └─ prev_y = 2. Find next...            │
  └───────────────────┬─────────────────────┘
                      │
                      ├─ Try connecting to 3. Domino (2,3) exists.
                      │
                      ▼
                    ┌─────────────────────────────────────────┐
                    │ `recursive(chain=[(1,2),(2,3)], first=1)`│
                    │  └─ prev_y = 3. Find next...            │
                    └───────────────────┬─────────────────────┘
                                        │
                                        ├─ Try connecting to 1. Domino (3,1) exists.
                                        │
                                        ▼
                                      ┌──────────────────────────────────────────┐
                                      │ `recursive(chain=[(1,2),(2,3),(3,1)], ...)` │
                                      │  └─ table.len is 0. Base case hit.       │
                                      │  └─ last_y (1) == first_val (1) -> TRUE  │
                                      └───────────────────┬──────────────────────┘
                                                          │
                                                          ▼
                                                      [ SUCCESS ]
                                           Return Some(...) up the call stack.