In Part 1, we built a basic Train Tracks puzzle solver in C# using backtracking, honoring row/column counts and fixed pieces.

Now it’s time to take our solver to the next level:

✅ Enforce directional continuity between neighboring pieces
✅ Ensure a single continuous path connects all track segments

Let’s dive in.

🔁 Step 8: Add Directional Connection Logic

Each track piece connects in one or more directions. We define the allowed directions with a dictionary:

public static readonly Dictionary<PieceType, (int dr, int dc)[]> Connections = new()
{
    [PieceType.Horizontal] = new[] { (0, -1), (0, 1) }, // left ↔ right
    [PieceType.Vertical]   = new[] { (-1, 0), (1, 0) }, // up ↔ down
    [PieceType.CornerNE]   = new[] { (-1, 0), (0, 1) },
    [PieceType.CornerNW]   = new[] { (-1, 0), (0, -1) },
    [PieceType.CornerSE]   = new[] { (1, 0), (0, 1) },
    [PieceType.CornerSW]   = new[] { (1, 0), (0, -1) },
};

Before placing a piece, we check that for each direction it connects in, any filled neighbor also connects back.

🔗 Step 9: Validate Connections on Placement

In Grid.CanPlace, we:

  1. Match each new connection against existing neighbors.
  2. Reject any placement where the neighbor doesn’t connect back.
  3. Enforce board-edge rules (no dangling connections off the grid).
  4. This guarantees our tracks interlock correctly, just like real rails.

🔄 Step 10: Ensure a Single Connected Path

To confirm the entire solution is one path:

  1. Start at any filled cell.
  2. Traverse via DFS or BFS following valid connections.
  3. Mark visited cells.
  4. Verify that every non-empty, non-blocked cell was visited exactly once.
  5. We call this IsSingleConnectedPath() inside our IsComplete() check.

🛠️ Iterating for Performance

Our first algorithm, which searched for empty cells and tried to place peices, satisfying the constraints, would solve for our simple test cases (10x10 with a single horizontal line, for example), but not complete in over 30 minutes for a more real world example, which is considered small.

Here’s how we got it down to ~130 000 and sub-second runtimes:

1. Memoization (and its retirement)

We tried Zobrist hashing to skip previously seen board states—but once we refined our heuristics, it no longer provided benefit, so we disabled it.

2. Priority-Queue on Empty Cells

Instead of scanning row by row, we built a min-heap of empty cells keyed by the number of legal placement options. Always solving the “hardest” cell first reduced branching significantly.

3. Adjacency-Focused Priority Selection

We refined our PQ to prioritize cells adjacent to already placed tracks. This guided the solver along the growing path rather than wasting work in isolated regions. Now we could solve the simple puzzle we previously failed to find a solution for in about 5 seconds, with 2.6 million attempts!

4. Look-ahead in CanPlace

Added a check that every direction a new piece will connect into must still have capacity in its row/column. This immediately pruned impossible “must continue” placements and cut attempts to ~130,000, and sub-second solves!

🔜 Next Steps: Profiling & Beyond

In Part 3, we’ll explore profiling tools to identify any remaining hot-spots, and discuss ways to visualize or export solutions. Stay tuned!

👍 Found this series helpful? Share your own puzzles and performance tips with @ProfByteCodes!