Train Tracks Part 3: A Path-Based Solver

In Parts 1 and 2, we painstakingly built and optimized a backtracking solver:

• Built a basic backtracking solver with row/column constraints (Part 1)
• Added directional checks, look-ahead pruning, a priority queue, and adjacency heuristics—getting our small 5×5 sample down to ≈130 000 attempts (Part 2)

All that work was valuable, but the biggest leap came when we rethought the whole approach.

---

🔄 A New Perspective: Build the Path, Don’t Fill the Grid

Instead of scanning every empty cell, placing pieces, and backtracking across the board, the PathBuilderSolver:

1. Finds the two fixed “entry” pieces on the edges (with exactly one off-grid connector).
2. Starts at one entry and walks the path, placing or reusing fixed pieces as it goes.
3. Prunes early using:
   • A total-piece count check (never exceed the exact sum of all row counts).
   • A Manhattan-distance heuristic guiding the search toward the next unconnected fixed piece.
4. Stops once all fixed pieces are hit, the path exits the opposite edge, and every row/column count matches.

By focusing the search along the actual train line instead of exploring every grid cell, we cut out most of the wasted branching.

This solution is an implementation of a greedy best-first DFS with heuristics, not quite an *A*** algorithm. By adding more book keeping, we can turn it into an A implementation, maybe we’ll do that next.

---

🚀 Performance Comparison

Solver Type	Attempts	Solve Time*
Backtracking + Heuristics (Part 2)	≈130 000	~0.3 s
PathBuilderSolver	≈ 4 000	~0.02 s

* Times on a 5×5 test board running on a 2025 MacBook Pro.

25× fewer attempts and 15× faster just by steering the search along the path!

---

🔍 Code Snapshot

Here’s the core recursion for the PathBuilderSolver (fully in your repo):

bool TryBuild(int r, int c, (int dr, int dc) incoming, HashSet<(int,int)> visited, int fixedHit)
{
    // 1) Bounds, revisit, total-piece check
    if (!grid.IsInBounds(r,c) || visited.Contains((r,c)) || visited.Count >= totalCount)
        return false;

    // 2) Align with any fixed piece
    var existing = grid.Board[r,c];
    if (existing != PieceType.Empty)
    {
        if (!TrackConnections.ConnectsTo(existing, (-incoming.dr, -incoming.dc)))
            return false;
        fixedHit++;
    }
    visited.Add((r,c));

    // 3) Check completion: all fixed hit, back at edge, row/col counts match
    if (fixedHit == targetFixedCount && IsOnEdge(r,c) && grid.TrackCountInAllRowsColsMatch())
        return true;

    // 4) Guide next moves by Manhattan distance to remaining fixed pieces
    var remaining = fixedPositions.Where(fp => !visited.Contains(fp));
    foreach (var piece in CandidatePieces(r, c, existing))
    {
        if (existing == PieceType.Empty) grid.Place(r,c,piece);
        foreach (var dir in TrackConnections.GetConnections(piece)
                                       .Where(d => d != Reverse(incoming))
                                       .OrderBy(d => MinDistance(r+d.dr, c+d.dc, remaining)))
        {
            if (TryBuild(r+d.dr, c+d.dc, d, visited, fixedHit))
                return true;
        }
        if (existing == PieceType.Empty) grid.Remove(r,c);
    }

    visited.Remove((r,c));
    return false;
}

🧰 What We’ve Built

• ✅ Grid-based logic constraint solver
• ✅ Backtracking with pruning
• ✅ Direction-aware connections
• ✅ Path continuity validation
• ✅ Text format loading and ASCII output
• ✅ Optimized path based solver

This framework can now solve many real-world logic puzzles—and is a great stepping stone into building solvers for other games like Slitherlink, Pipes, or even Minesweeper.

---

Want to take it further?

• Add puzzle generation
• Build a web interface
• Compile into an online daily solver

📣 Tag @ProfByteCodes if you do—we’d love to see what you build!

🔗 Full code coming soon to GitHub.