Why Solve Puzzles in Minutes When You Can Code a Solution in Days? (2024)

About Railbound

Railbound is an enchanting puzzle game that follows two adorable dogs on a global train adventure. As a player, your mission is to connect and disconnect railways across diverse landscapes, ensuring everyone reaches their destination. This delightful game offers:

• Over 240 puzzles set in various parts of the world
• A range of train-inspired mechanics, including tunnels and semaphores
• Charming comic-book-style visuals
• A soothing original soundtrack to accompany your journey

For those interested in experiencing the full game, you can find more information on the official Railbound website.

Here are some captivating images from the game:

So how do you play this game?

This game is simpler than my attempts at cooking - there's a grid map, some tracks, and a bunch of trains having an identity crisis. Your job? Play track-laying fairy and fill in the empty spots so that when you hit that magical "play" button, all the trains choo-choo their way to the right spots in the correct order. Easy peasy lemon squeezy, right? WRONG! O.o

Let's peek at some early maps that lull you into a false sense of security:

See Also

Special Chests — Merge Magic! Help CenterChange in 2023 - A Chat with ChatGPT

"Oh, this is fun!" you'll say. Then BAM! Mid-game hits you like a runaway locomotive:

At this point, my brain cells were sending out SOS signals. So, like any reasonable human being, I thought, "Why solve puzzles when I can spend 10 times longer writing a script to solve them for me?" Logic: 100.

First Attempt: Brute Force Approach

In my initial attempt to solve Railbound puzzles programmatically, I opted for the simplest solution: brute force. The idea was to try all possible combinations of tracks and check if any of them solved the puzzle. To implement this, we need to understand the types of tracks available in the game.

Track Types

After playing the game for a while (and maybe losing track of time once or twice), you'll notice that there are only three basic types of tracks, but they can be rotated and flipped in various ways:

These basic types can result in many variants:

We can index these tiles from 1 to 14, with 0 representing an empty space. This allows us to represent a game grid as a 2D array of integers:

[[0, 5, 0, 0, 0, 5, 0],[0, 5, 0, 6, 0, 5, 0],[0, 0, 3, 0, 4, 0, 0],[0, 0, 0, 6, 0, 6, 0],[0, 0, 2, 0, 1, 0, 0],[0, 5, 0, 6, 0, 5, 0],[0, 5, 0, 0, 0, 5, 0]]

Thanks to Foxtrot for the images of the tracks used in the game.

Generating All Possible Grids

To generate all possible grid configurations, we can use a depth-first search (DFS) or breadth-first search (BFS) algorithm. However, I prefer using Python's itertools for a cleaner implementation:

def generate_grids(grid, max_replacements): # Find indices of 0s in the grid zero_indices = [(i, j) for i, row in enumerate(grid) for j, val in enumerate(row) if val == 0] # Generate all possible combinations of replacements for r in range(min(max_replacements, len(zero_indices)) + 1): for indices in itertools.combinations(zero_indices, r): for replacements in itertools.product(range(1, 15), repeat=r): new_grid = [row[:] for row in grid] # Create a deep copy of the grid for (i, j), value in zip(indices, replacements): new_grid[i][j] = value yield new_grid# Example usageinitial_grid = [[6, 0, 0, 6]]max_replacements = 2for grid in generate_grids(initial_grid, max_replacements): print(grid)

This generates a list of all possible grid configurations:

Simulating Train Movement

After generating all possible track configurations, we need to simulate train movement to determine which configurations lead to successful solutions. Here's how we approach this simulation:

Core Simulation Loop

The heart of our simulation is a loop that continues until a solution is found or a maximum number of iterations is reached:

while max_iterations > 0: for each train: move train check for crashes check if destination reached check for collisions between trains check if trains reached destinations in order if all trains at correct destinations: break loop (solution found) max_iterations -= 1

Train Movement

For each train, we:

1. Update its position based on its current direction
2. Determine the new direction based on the track it moves onto

Track Representation

To simplify direction changes, we represent each track type as a set of input-output direction pairs. For example:

• Straight track: (up, up), (down, down), (left, left), (right, right)
• 90-degree turn: (up, right), (right, down), (down, left), (left, up)

This allows us to easily determine a train's new direction after moving onto a track.

Crash Detection

We check for two types of crashes:

1. Train moves out of the grid bounds
2. Train moves onto an invalid track (e.g., trying to go up on a horizontal-only track)

Collision Detection

After moving all trains, we check if any two trains occupy the same position, indicating a collision.

Destination Order Checking

We verify that trains reach their destinations in the correct order. If a train reaches its destination before previous trains in the sequence, it's considered an invalid solution.

Termination Conditions

The simulation terminates when:

1. All trains reach their destinations in the correct order (solution found)
2. A train crashes or a collision occurs (invalid configuration)
3. The maximum number of iterations is reached (prevents infinite loops)

Preventing Infinite Loops

To avoid situations where trains might circle endlessly without reaching their destinations, we set a maximum number of iterations:

max_iterations = some_reasonable_numberwhile max_iterations > 0: # ... simulation logic ... max_iterations -= 1

This ensures the simulation will eventually terminate, even if no solution is found.

Running the Solver

Now that we've got our simulation up and running, it's time to unleash it on some Railbound levels and watch the magic happen!

Look at it go! It's like watching a hyperactive squirrel trying to decide which acorn to grab first. Promising, right? Well, hold onto your engineer's cap, because we're about to hit a snag.

We have a problem...

Everything's chugging along nicely until we reach some special level. Suddenly, our solver decides to take a leisurely stroll through the space-time continuum. Why? Let's break it down:

Let look at the result of the solver:

At level 1-6, we check 518467 possibilities to find the solution. At level 1-9, we check 5 million possibilities. That's a lot of possibilities to check, and it's only going to get worse as we tackle more complex levels.

Consider the following level 1-6:

Let's Have Some Calculations:

1. We have 13 empty spaces and 3 tracks to fill. That means we have:

   $$\binom{13}{3} = \frac{13!}{3!(13-3)!} = \frac{13 \times 12 \times 11}{3 \times 2 \times 1} = 286 \text{ combinations}$$(313​)=3!(13−3)!13!​=3×2×113×12×11​=286combinations

2. We have 3 types of tracks, but 14 variants in total. So for the first position, we have 14 possibilities.

3. For the second position, it's $14\times14 = 14^2 = 196$14×14=142=196 possibilities.

4. By the third position, we're up to $14\times14\times14=14^3 = 2744$14×14×14=143=2744 possibilities.

5. That means for each 3 positions, 2744 possibilities to check. And for 286 combinations of 3 positions, we have:

   $$2744 \times 286 = 785584 \text{ possibilities}$$2744×286=785584possibilities

Now, imagine you need to place 15 tracks with 30 empty spaces. That's about:

Estimating Computer Time:

To put this number into perspective, let's estimate how long it would take a computer to process all these possibilities:

1. Assume a modern computer can check 1 billion (10^9) possibilities per second.

2. Time required = (Number of possibilities) / (Possibilities checked per second)

   $$\text{Time} = \frac{2.41 \times 10^{25}}{10^9} = 2.41 \times 10^{16} \text{ seconds}$$Time=1092.41×1025​=2.41×1016seconds

3. Converting to years:

   $$\text{Years} = \frac{2.41 \times 10^{16}}{60 \times 60 \times 24 \times 365.25} \approx 764 \text{ million years}$$Years=60×60×24×365.252.41×1016​≈764millionyears

That's more than 150 times the age of the dinosaurs! Even if we could use a supercomputer that's a million times faster, it would still take 764 years.

This astronomical number of possibilities demonstrates why brute-force approaches quickly become impractical for complex optimization problems. It's a prime example of why we need clever algorithms and heuristics to tackle such challenges efficiently.

Enter: Branch and Bound

Instead of exhaustively exploring every possible track configuration (and potentially creating a few alternate universes in the process), we're taking a smarter approach. Enter branch and bound, a clever technique that allows us to prune our search space and avoid unnecessary exploration.

Our strategy is to place tracks strategically, ensuring each new piece connects to the existing network. This approach dramatically reduces the number of configurations we need to evaluate. Here's a glimpse of our optimized generate_grids function:

def generate_grids(grid, max_replacements): def _generate_grids(grid, max_replacements): if max_replacements == 0: yield grid return for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == 0: for track in range(1, 15): # this function checks if the track connects to the existing network if check_track_connect_to_existing(grid, i, j, track):  new_grid = [row[:] for row in grid] new_grid[i][j] = track yield from _generate_grids(new_grid, max_replacements - 1) yield from _generate_grids(grid, max_replacements)

Now, let's put our new solver to the test:

Well, would you look at that! Our solver went from "heat death of the universe" to "I'll be done before your coffee gets cold." This is definitely better, but as any true puzzle enthusiast knows, there's always room for improvement.

So till the next time, when we dive deeper into the world of Railbound and unravel more mysteries, keep those tracks aligned and your trains on time!

Note: in this post I only solve the first level of the game. The game have total 12 levels, on the future post I will solve all of them. Stay tuned!

You can check the full code on my GitHub. Or join the discussion on Discord where me and some other people are discussing about the game and the solver.