“@ProfByteCodes How would you go about solving these programmatically?” — @SteveHuwJohn, referencing puzzlemadness.co.uk/traintracks

In this three‑part series, we took on the challenge of building a train track puzzle solver from scratch. Below is a quick tour of our journey:

Part 1: Representing the Puzzle

In our first post, we introduced the problem domain and laid out a brute‑force strategy that explores every possible path through the grid. We covered:

  • Grid representation: How to model the puzzle board as nodes and edges.
  • Backtracking approach: Recursively extending paths until a complete loop is found.
  • Basic serialization: Loading puzzles from file, easier than hard-coding!

Read more → Train Tracks Solver Part 1

Part 2: Priority-Queue Based Solver

In the second installment, we implemented a complete solver which checks we have a continuous path. We also discuss how we optimized it, and ended up with something which wasn’t uterly terrible!

  • Directional Logic: Defining how track pieces connect.
  • Validating Placement: Ensure we only place pieces which connect correctly.
  • Ensuring a Connected Path: Making sure we solve the problem!
  • Optimization Techniques: How we sped it up, and resulted in sub-second solving capabilities with a Priority Queue solver!

Read more → Train Tracks Solver Part 2

Part 3: Rethinking our Solver for the win!

Our final post we rethought our strategy and implemented a Path Based solver which was quicker and more efficient.

Read more → Train Tracks Solver Part 3

What’s Next?

Since publishing the series, we’ve:

  • Implemented a third solver: Based on the /posts/2025/04/17/a-star/ algorithm, can it beat the path solver?
  • Added a Generator: Produce random puzzles of configurable size and complexity.
  • Benchmark Mode: Compare solve times across different heuristics and implementations.
  • Community Collaboration: Helped @SteveHuwJohn debug his own solver and collected feedback to improve ours.

Solver Leaderboard

Below is a placeholder for our current leaderboard of best solve times.

These were generated on a 2025 M4 MacBook Pro using the following command:

dotnet run -c Release -- -p Puzzles.json -b -m path,astar --timeout 1000
# Rows x Cols Solver Iterations Time (ms) Solved
1 12x12 path 30,547,824 14,143 Yes
1 12x12 astar 44,096,048 343,795 Yes
2 11x12 path 3,848,513 1,829 Yes
2 11x12 astar 7,886,810 56,305 Yes
3 11x11 path 604,317 287 Yes
3 11x11 astar 433,134 3,033 Yes
4 12x11 path 1,402,056 641 Yes
4 12x11 astar 1,177,883 8,123 Yes
5 6x6 path 210 0 Yes
5 6x6 astar 322 0 Yes
6 6x6 path 119 0 Yes
6 6x6 astar 159 0 Yes
7 9x9 path 208,978 89 Yes
7 9x9 astar 158,632 693 Yes
8 9x9 path 690 0 Yes
8 9x9 astar 395 1 Yes
9 10x10 path 1,621 0 Yes
9 10x10 astar 2,016 11 Yes
10 11x12 path 583,354 277 Yes
10 11x12 astar 557,723 4,125 Yes
11 6x7 path 964 0 Yes
11 6x7 astar 744 2 Yes
12 12x11 path 254,592 126 Yes
12 12x11 astar 694,030 5,538 Yes
13 12x12 path 1,068,800,127 496,306 Yes
13 12x12 astar 870,157,161 39,626,338 Yes

Source Code and Repository

All of the code—solvers, benchmarks, and the puzzle generator—is available on GitHub:

https://github.com/professorbyte-codequest/train-track-solver/tree/main

Feel free to clone, experiment, and contribute! Happy coding, and may your tracks always connect.