Solving Flow Free with Python and Rust

- 7 mins
Python Rust Flow Games

About a month ago, I started working on a project to solve Flow puzzles, like these:

I had been thinking of doing this for a while, but I finally had the time to do it. So of course I start by taking the hard route: one of my initial goals for the project was to use image processing to read puzzles, and not rely on having to manually convert the puzzles. To do this, I used OpenCV-Python. After quite a bit of trial and error, I settled on the following process for reading images:

  1. Start with a screenshot:
  1. Convert to grayscale:
  1. Use a binary threshold to make finding the lines easier:
  1. Use HoughLines to find the lines of the grid:
  1. Using the found lines (which provide the height and width of the puzzle), determine the color at the center of each cell (this image is really just for demonstration purposes):

After matching colors from step 5, the puzzle is now in the format of a 2D array of strings, either a ‘-‘ for blank cells or a letter specifying which flow it belongs to. The code for the image processing is here. It also is the main file for the python solver.

Now for the solving part. I got a lot of the ideas (mostly for how to eliminate bad moves) for this part from Matt Zucker. Basically, the concept boiled down to:

  1. Given a puzzle state, pick a flow to extend
  2. Generate all possible (one-cell) extensions for that flow
  3. Looping through each child:
    1. If the child is solved, return it
    2. Recursively solve on the child
    3. If the recursive step returns a solution, return that
  4. Return None

There are two main (maybe three) main problems to address here: 1) How to pick a flow to move next and 2) How to minimize the number of children visited. The first one is simpler (thanks to Zucker): simply choose the endpoint with the fewest possible extensions. As Zucker points out, this also reduces the branching factor, serving to minimize the number of nodes visited. The second involved attempting to score children by determining which was the most likely to be the parent of a solution and prioritizing these during step 3. Scores were determined by various factors, including the number of flows completed, whether there are any impossible situations, and the average distance remaining between flow endpoints.

In the end, this worked - mostly:

The solver was able to complete several boards (and even create gifs of it solving them), but it had a limit. On any puzzle larger than ~9x9, it would reach python’s recursion limit. It also couldn’t solve Flow’s newer puzzles, like bridges, hexes, or flows.

So I decided I wanted to try using what I had learned, and a different language, to create a better solver. My initial thoughts went to Java or C++, as I know both and am definitely more familiar with the object-oriented nature of them than I am with Python. But for some reason, and I don’t remember why, I went with Rust, a language I had never touched and had barely even read about. After familiarizing myself with the language and experimenting a bit, I was off.

I initially followed the same strategy for solving as I did with the python version, I just organized it better, and made a few key changes:

  1. Eliminated image processing (at least for now). If I was going to solve Flow’s other types of puzzles, I would have to put off reading them from screenshots a bit. My limited knowledge with Rust isn’t compatible with my limited knowledge of image processing (and my brief research showed that image processing in rust is still fairly new).
  2. To allow for 1, I had to define an input format that allowed for all types of boards - see the [project README] (https://github.com/samgoldman/flow-solver) for more details. Hexes got messy, but it worked.
  3. Puzzles are now stored in the form of interconnected nodes: each node has a set of defined neighbors. This was the biggest and most important change. It allowed for hexes (6 neighbors), bridges (although I was dumb and handled these stupidly at first), and warps (neighbors on the opposite side).
    1. Aside from being able to handle other board types, this allowed for far easier manipulation of the board and made it far simpler to determine, for example, how many empty neighbors a cell had.
    2. This was actually kind of difficult considering Rust’s ownership rules (but these rules probably saved me tons of time in the end.

With this, I initially followed the same recursive algorithm (sans the sorting, as I was fighting with Rust’s ownership rules at the time). And it worked, but actually less so. Because I was unable to figure out sorting (and perhaps a few other reasons), solving the puzzles took longer, and on the 9x9 puzzle that definitely took the python a while to solve, my computer blue screened when running the Rust version on it. I ran it again, monitoring memory usage - it was using up all of my computer’s memory. I’m still not 100% sure what the cause of this problem was, but at the time, I set the project aside for a few days.

After getting a few ideas from my AI class, I returned to the project, scrapping the recursive strategy. Instead, I used what I think is a greedy-best first search algorithm:

  1. Create a priority queue of puzzle states to visit (and add the initial state to it
  2. Pop the highest priority state and pick a flow in it to extend (same principle as above)
  3. Generate all possible children for that state and the picked flow
  4. For each child, if the child is solved, return it, otherwise if it is still solvable, add it to the queue
  5. Go to 1

The big thing here is determining if a puzzle is still solvable, and this is where my organization with nodes came in handy. I was able to check if dead ends or pools exist, whether regions have no possible solution due to lacking a matching pair of flow endpoints, or if flows endpoints done have a region in common (all of these checks came from Zucker). In the end, I was able to solve some 14x14 puzzles in 10 seconds (and another which takes a few hours). The key was that I almost never stored more than 200 puzzle states at a time.

Other things I learned:

  1. Don’t over complicate things. When initially planning for handling bridges, I designed the nodes for cells as having a potential second occupying flow (the same cell had two flows). This made all of the logic regarding these cells complicated, most significantly regarding whether a partially full bridge cell was counted as full or empty for a given circumstance. When doing some other simplification, I realized that I could split bridge cells into two “overlapping” cells - one vertical and one horizontal - each with only two neighbors. This eliminated a lot of redundancies in the code.
  2. The Rust borrow checker can be frustrating, but once you realize how it works, it really makes you think about how you are handling and modifying data. I do think it made my design choices better, even if C++ or Java would have made solutions easier to write.
  3. I really like solving puzzles.

Ideas going forward:

  1. Improve solving for hexes - there are a couple of impossibility checks that were causing issues for hexes, so I disabled them. I want to figure those out, which would make solving hexes more efficient.
  2. Image processing! Especially for hexes (which of course would be a nightmare), because transcribing these by hand is a nightmare.
  3. Animations - this would probably have to come after 2.