---

Clojure Connect Game: A Zero-to-Hero Guide to Pathfinding Algorithms

Solving the Connect game in Clojure involves determining a winner by implementing a graph traversal algorithm, such as Depth-First Search (DFS). The core task is to find an unbroken path of a player's stones connecting their designated opposite sides of the hexagonal game board, a classic problem elegantly solved with functional programming.

You've seen it before: a game board, seemingly chaotic with black and white stones. To the human eye, spotting a winning line can take intense focus. But how does a machine see it? How can you write code that navigates this complex web of connections and declares a victor with absolute certainty? Many developers hit a wall when faced with graph and pathfinding problems, getting lost in mutable state, complex loops, and off-by-one errors. It feels like trying to find your way out of a maze blindfolded.

This is where the functional paradigm, and specifically Clojure, shines. By treating the board as immutable data and the search as a pure function, we can transform this confusing maze into an elegant, recursive journey. In this guide, we'll break down the Connect game, build a robust Clojure solution from scratch using Depth-First Search, and reveal how functional principles make solving such complex problems not just possible, but intuitive.

---

What is the Connect Game? The Fundamentals of Hex

Before diving into code, we must understand the battlefield. The "Connect" problem, as presented in the kodikra.com learning path, is based on a classic abstract strategy board game called Hex. The rules are deceptively simple, yet they give rise to profound strategic depth.

The game is played on a parallelogram-shaped grid of hexagons. Two players, 'X' (often Black) and 'O' (often White), take turns placing a stone of their color on an empty hexagon.

• Player 'X' Goal: To create an unbroken chain of 'X' stones connecting the top edge of the board to the bottom edge.
• Player 'O' Goal: To create an unbroken chain of 'O' stones connecting the left edge of the board to the right edge.

The first player to complete their path wins. One of the most fascinating properties of Hex is that it can never end in a draw. A completed game will always have a winner. Our task is to write a function that, given a final board state, can determine who that winner is.

The board is represented as a vector of strings, where each string is a row. For example:

(def board
  ["O O . ."
   " X X X ."
   "  . . . ."
   "   . O O O"
   "    . . . ."])

Our algorithm needs to treat this grid not as a simple 2D array, but as a graph where each hexagon is a node and adjacent hexagons of the same color are connected by an edge.

---

Why Clojure is the Perfect Tool for Graph Traversal

You could solve this problem in any language, but Clojure offers a unique set of advantages that make the solution particularly elegant and robust. Its functional-first nature aligns perfectly with the logic of graph algorithms.

• Immutability: The game board never changes during our analysis. In Clojure, data structures are immutable by default. This completely eliminates a whole class of bugs related to state mutation. We can pass the board state through our functions with confidence, knowing it won't be accidentally altered.
• Recursion as a First-Class Citizen: Pathfinding algorithms like Depth-First Search are inherently recursive. Clojure's design encourages and optimizes for recursion, making the implementation feel natural and declarative rather than imperative and complex.
• Powerful Data Structures: Clojure provides rich, efficient data structures out of the box. We will heavily leverage vectors for board access, sets for tracking visited nodes (providing near-instant lookups), and keywords for representing players.
• Conciseness: The final code is often remarkably concise. Clojure's expressive syntax and rich standard library allow us to focus on the core logic of the algorithm rather than boilerplate code.

By embracing these features, we can build a solution that is not only correct but also easy to reason about and maintain. Let's start by modeling the board and its unique hexagonal connections.

---

How to Solve It: Modeling the Board and Finding a Path

The core of the solution lies in two parts: first, correctly identifying the neighbors of any given hexagon, and second, implementing an algorithm to traverse these connections in search of a winning path. We'll use Depth-First Search (DFS), a classic and intuitive algorithm for this task.

Step 1: Understanding Hexagonal Coordinates

A standard square grid has 4 or 8 neighbors. A hexagonal grid is different. Each hex tile has six neighbors. Given a coordinate [row col], its neighbors can be found at these relative positions:

• [row-1, col] (Top-Left)
• [row-1, col+1] (Top-Right)
• [row, col-1] (Left)
• [row, col+1] (Right)
• [row+1, col] (Bottom-Right)
• [row+1, col-1] (Bottom-Left)

It's crucial to implement a helper function that, given a coordinate, returns a list of these six potential neighbors. We will also need a way to check if these coordinates are actually within the board's boundaries.

Step 2: The Depth-First Search (DFS) Algorithm

DFS works by exploring as far as possible down one path before backtracking. Imagine you're in a maze and you always take the first available path at every junction. You only turn back when you hit a dead end. For our game, a "path" is a chain of connected stones of the same color, and a "dead end" is a stone with no unvisited neighbors of the same color.

To prevent going in circles, we must keep track of the hexagons we've already visited. A set is the perfect data structure for this, offering fast additions and lookups.

Here is the logical flow of our DFS algorithm:

    ● Start DFS at a given coordinate `[r, c]`
    │
    ├─ Add `[r, c]` to the `visited` set
    │
    ▼
  ┌───────────────────────────┐
  │ Is `[r, c]` a goal tile?  │
  │ (e.g., in the last row/col) │
  └────────────┬──────────────┘
               │
      Yes ─────┤
               │
               ▼
           ┌────────┐
           │ Return │
           │ `true` │  // Path Found!
           └────────┘

               │
       No ─────┤
               │
               ▼
  ┌─────────────────────────────────┐
  │ Get all 6 neighbors of `[r, c]` │
  └─────────────────┬───────────────┘
                    │
                    ▼
  ┌───────────────────────────────────────────┐
  │ Filter for valid neighbors:               │
  │  - Inside board boundaries?               │
  │  - Not already in `visited` set?          │
  │  - Belongs to the current player?         │
  └───────────────────┬───────────────────────┘
                      │
                      ▼
    ◆ Any valid neighbors left?
   ╱                           ╲
  Yes                           No
  │                              │
  ▼                              ▼
┌─────────────────────────┐   ┌──────────┐
│ For each valid neighbor,│   │ Return   │
│ recursively call DFS.   │   │ `false`  │ // Dead End
└──────────┬──────────────┘   └──────────┘
           │
           ▼
┌─────────────────────────┐
│ If any recursive call   │
│ returns `true`, then... │
└──────────┬──────────────┘
           │
           ▼
       ┌────────┐
       │ Return │
       │ `true` │
       └────────┘

Step 3: The Overall Winner-Checking Logic

The DFS function can tell us if a path exists from a single starting point. To find the winner, we must apply this logic systematically:

1. Check for Player 'X': Iterate through every position in the first row. If a position contains an 'X', start a DFS from there. If any of these DFS searches return true (meaning they reached the bottom row), then 'X' is the winner.
2. Check for Player 'O': If 'X' has not won, iterate through every position in the first column. If a position contains an 'O', start a DFS from there. If any of these searches return true (meaning they reached the rightmost column), then 'O' is the winner.
3. No Winner: If neither player has a winning path, there is no winner on the current board.

This high-level process orchestrates our core pathfinding algorithm to solve the problem completely.

    ● Start `winner` function with the board
    │
    ▼
  ┌──────────────────────────┐
  │ Check for Player 'X' win │
  └────────────┬─────────────┘
               │
               ├─ For each cell in the top row...
               │
               ▼
          ◆ Is cell == 'X'?
         ╱                 ╲
       Yes                  No
        │                    │
        ▼                    │
    ┌──────────┐             │
    │ Run DFS  │             │
    └─────┬────┘             │
          │                  │
          ▼                  │
    ◆ Path found?            │
   ╱           ╲             │
  Yes           No           │
  │              │           │
  ▼              ▼           ▼
┌──────────┐   Loop to     Continue
│ Return 'X' │   next cell   to Player 'O'
└──────────┘
    │
    ▼
  ┌──────────────────────────┐
  │ Check for Player 'O' win │
  └────────────┬─────────────┘
               │
               ├─ For each cell in the left column...
               │
               ▼
          ◆ Is cell == 'O'?
         ╱                 ╲
       Yes                  No
        │                    │
        ▼                    │
    ┌──────────┐             │
    │ Run DFS  │             │
    └─────┬────┘             │
          │                  │
          ▼                  │
    ◆ Path found?            │
   ╱           ╲             │
  Yes           No           │
  │              │           │
  ▼              ▼           ▼
┌──────────┐   Loop to     Return `nil`
│ Return 'O' │   next cell   (No Winner)
└──────────┘

---

The Complete Clojure Solution

Now, let's translate our logic into idiomatic Clojure code. We'll structure our solution within a namespace and build it up with helper functions for clarity and reusability. The code is heavily commented to explain each part of the process.

(ns connect)

(defn- get-board-dims
  "Calculates the dimensions (height, width) of the board."
  [board]
  (let [board (mapv #(.replaceAll % " " "") board)] ; Remove spaces for accurate width
    [(count board) (count (first board))]))

(defn- get-char-at
  "Safely retrieves the character at a given [row col] coordinate."
  [board [row col]]
  (let [[height width] (get-board-dims board)]
    (when (and (>= row 0) (< row height) (>= col 0) (< col width))
      (let [clean-board (mapv #(.replaceAll % " " "") board)]
        (get-in clean-board [row col])))))

(defn- get-neighbors
  "Returns the six hexagonal neighbors for a given coordinate [r c]."
  [[r c]]
  [[(dec r) c]      ; Top-Left
   [(dec r) (inc c)]  ; Top-Right
   [r (dec c)]      ; Left
   [r (inc c)]      ; Right
   [(inc r) c]      ; Bottom-Right
   [(inc r) (dec c)]]); Bottom-Left

(defn- find-path?
  "Main recursive DFS function to find a path for a player.
   - board: The game board.
   - player: The character to search for ('X' or 'O').
   - is-goal?: A function that returns true if a coordinate is a winning position.
   - current-pos: The current [row col] coordinate to explore.
   - visited: A set of coordinates already visited to prevent cycles."
  [board player is-goal? current-pos visited]
  (cond
    ;; Base Case 1: If we've already visited this position, stop.
    (contains? visited current-pos)
    false

    ;; Base Case 2: If the character at the current position is not our player, stop.
    (not= (get-char-at board current-pos) player)
    false

    ;; Base Case 3: If this position is a goal position, we've found a path!
    (is-goal? current-pos)
    true

    ;; Recursive Step: Explore valid, unvisited neighbors.
    :else
    (let [new-visited (conj visited current-pos)
          neighbors (get-neighbors current-pos)]
      ;; 'some' short-circuits, returning true on the first successful path found.
      (some #(find-path? board player is-goal? % new-visited) neighbors))))

(defn winner
  "Determines the winner of the Connect game.
   Returns :X, :O, or nil if there is no winner."
  [board]
  (let [[height width] (get-board-dims board)]
    (cond
      ;; Check for Player 'X' win (Top to Bottom)
      (some (fn [col]
              (find-path? board \X #(= (first %) (dec height)) [0 col] #{}))
            (range width))
      :X

      ;; Check for Player 'O' win (Left to Right)
      (some (fn [row]
              (find-path? board \O #(= (second %) (dec width)) [row 0] #{}))
            (range height))
      :O

      ;; No winner found
      :else
      nil)))

Detailed Code Walkthrough

Let's dissect this solution piece by piece to understand how it all works together.

1. Helper Functions: get-board-dims, get-char-at, get-neighbors

These functions handle the basic mechanics of interacting with our board data structure.

• get-board-dims: This simply calculates the height and width. Crucially, it first removes spaces from the input strings to get an accurate character count for the width.
• get-char-at: A safe way to access a character at a coordinate. It performs bounds checking, returning nil if the coordinate is off the board. This prevents IndexOutOfBoundsException errors.
• get-neighbors: The direct implementation of our hexagonal coordinate logic. It takes a coordinate vector and returns a list of the six potential neighbor coordinates.

2. The Core Logic: find-path?

This is our recursive DFS implementation. It's the heart of the solution.

• Arguments: It takes the board, the player character we're searching for, an is-goal? function, the current-pos, and the visited set. Passing is-goal? as a function makes our DFS generic and reusable for both players.
• Base Cases: The cond statement handles the conditions that stop the recursion.
  1. (contains? visited current-pos): If we've been here before, we stop to avoid an infinite loop.
  2. (not= (get-char-at board current-pos) player): If the current tile doesn't belong to our player, it's a dead end. This also handles out-of-bounds coordinates, as get-char-at returns nil.
  3. (is-goal? current-pos): If the current position satisfies the winning condition (e.g., it's in the last row for 'X'), we've succeeded and return true all the way back up the call stack.
• Recursive Step: If no base case is met, we add the current position to a new visited set (new-visited) to maintain immutability. We then get all neighbors and use some to recursively call find-path? on them. some is perfect here because it stops and returns the first "truthy" value it finds. If any neighbor leads to a winning path, the whole expression becomes true. If all neighbors lead to dead ends, some returns nil (which is "falsey"), and the function returns false.

3. The Orchestrator: winner

This function sets up and initiates the search for each player.

• It first determines the dimensions of the board.
• Player 'X' Check: It uses some to iterate through the column indices of the first row ((range width)). For each starting position [0 col], it kicks off a find-path? call. The goal function for 'X' is #(= (first %) (dec height)), which checks if a coordinate's row is the last row. If any of these starting points result in a win, some returns true, the cond clause is satisfied, and the function immediately returns :X.
• Player 'O' Check: This is only executed if the 'X' check fails. It's analogous, but it iterates through the row indices of the first column ((range height)). The goal function for 'O' is #(= (second %) (dec width)), which checks if a coordinate's column is the last column. If a path is found, it returns :O.
• Default: If neither check succeeds, the :else clause returns nil.

---

Alternative Approaches and Performance

While DFS is an excellent and intuitive choice, it's not the only way to solve this problem. Understanding the alternatives helps in choosing the right tool for different scenarios.

Pros & Cons: DFS vs. BFS

Breadth-First Search (BFS) is another common graph traversal algorithm. Instead of going deep, it explores level by level. Here’s how they compare for this problem:

Algorithm	Pros	Cons
Depth-First Search (DFS)	Generally uses less memory (stores only the current path). Often simpler to implement with recursion, which is very idiomatic in Clojure.	Does not guarantee the shortest path (not a requirement for this problem). Can get lost in very long, fruitless paths on large, complex graphs.
Breadth-First Search (BFS)	Guaranteed to find the shortest path from the start to the goal. Can be more efficient if the winning path is short and wide.	Typically more memory-intensive as it needs a queue to store all nodes at the current frontier. Often implemented iteratively with a queue, which can feel less natural in a functional style than recursion.

For the Connect game, since we only care about the existence of a path and not its length, DFS is a perfectly valid and often simpler choice. The memory advantage can be significant on larger boards.

---

Frequently Asked Questions (FAQ)

Why is recursion a good fit for this problem in Clojure?

Recursion naturally models the "explore and backtrack" nature of Depth-First Search. Each recursive call represents stepping to a new node in the graph. Clojure's emphasis on immutability means we pass state (like the `visited` set) as arguments to the next function call rather than modifying a global variable. This avoids side effects and makes the logic much easier to reason about and debug.

What is the role of the `visited` set in the DFS algorithm?

The `visited` set is critical for correctness and performance. It acts as the algorithm's memory, preventing it from exploring the same node twice. Without it, the algorithm could get stuck in an infinite loop by moving back and forth between two adjacent nodes, leading to a `StackOverflowError` in a recursive implementation.

Can the game of Hex (Connect) ever end in a draw?

No. This is a proven mathematical property of the game. A draw is impossible. At the end of any fully-played game, there will always be a winning path for one of the two players. This is related to the Brouwer fixed-point theorem and means our function doesn't need to handle a "draw" state on a full board, only a "no winner yet" state on a partial board.

How would you adapt this code for a different board size?

Our code is already fully adaptable to any board size. The dimensions are calculated dynamically by the `get-board-dims` function. The starting points and goal conditions are also determined dynamically based on these dimensions (e.g., `(dec height)`). You can pass a board of any rectangular parallelogram shape, and the logic will hold.

What are the time and space complexities of this DFS solution?

Let N be the number of hexagons on the board (Height * Width).

• Time Complexity: O(N). In the worst case, the algorithm might have to visit every single hexagon on the board once. Because we use a `visited` set, we never process a hexagon more than once.
• Space Complexity: O(N). In the worst case, the recursion depth could be equal to the total number of hexagons (a single long, winding path). Each recursive call adds a frame to the call stack, so the space used is proportional to the length of the path being explored.

Why are there six neighbors for a hex tile instead of four or eight?

This is a fundamental property of a hexagonal tiling (a grid made of hexagons). Unlike a square, which has four cardinal neighbors (up, down, left, right) and four diagonal ones, a hexagon has six sides. Each side touches exactly one other hexagon, resulting in six direct neighbors. Our coordinate system is a way to map this geometric reality to a 2D array representation.

---

Conclusion: From Chaos to Clarity with Functional Programming

We successfully navigated the complexities of the Connect game, transforming a challenging pathfinding problem into a clean, understandable, and robust Clojure solution. By leveraging immutable data, pure functions, and the natural elegance of recursion, we built an algorithm that can dissect any board state and declare a winner with confidence.

The key takeaway is not just the code itself, but the underlying approach. Thinking functionally allowed us to manage complexity by breaking the problem into small, verifiable pieces: modeling neighbors, defining a goal, and expressing the search as a recursive journey. This pattern is incredibly powerful and can be applied to a wide range of algorithmic challenges.

This exercise from the kodikra learning path is a fantastic demonstration of how to apply core computer science concepts in a real-world scenario. To continue your journey, you can explore more graph problems or deepen your understanding of functional programming with our complete Clojure guide.

Disclaimer: The solution provided is written against Clojure 1.11+. While the core logic is timeless, specific function calls and idioms are reflective of modern Clojure practices.

---

Published by Kodikra — Your trusted Clojure learning resource.