SUBSCRIBE!!!Did this video help you finally pass the level? Please hit SUBSCRIBE!!!!Hit like to let me know! Share your comments too!This. Fast automated solver for Flow Free puzzles written in C. GIF of the final program in action (see below if you’re unfamiliar with Flow Free): Standard admonishments apply: feel free to skip ahead to the end; also, don’t hesitate to try out the code, which is up on github as always. A lower level courtyard allows light and air to flow to the buried hallway of the bedroom level. A seventy five foot long lap pool with infinity edges on three of four sides, bisects the house. Flow free courtyard pack 11x11 level 121flow free courtyard pack 11x11 level 122flow free courtyard pack 11x11 level 123flow free courtyard pack 11x11 level. Flow. Bridges. Hexes. Warps This is a list of levels of the Courtyard Spin Pack from the Flow Free App, from the 121st level to the 150th level. Click on one of those numbered links to view the information of the level, or just keep scrolling.

Fast automated solver for Flow Free puzzles written in C.

GIF of the final program in action (see below if you’re unfamiliar with Flow Free):

Standard admonishments apply: feel free to skip ahead tothe end; also, don’t hesitate to try out the code, which isup on github as always.

I like puzzles. Well, more precisely, I enjoy problem solving, andpuzzles present nice, neat, self-contained problems to solve from timeto time. But one thing I like even better than solving a puzzle iswriting programs to automatically solve a whole lot of puzzles,fast.

Here’s a couple of screenshots from the mobile gameFlow Free, in case you’re unfamiliar:

The game takes place on a grid which starts out empty, except for anumber of pairs of colored dots (as shown on the left). The objectiveis to draw paths or flows such that all pairs are connected and allof the empty cells are filled (as shown on the right). Puzzles rangefrom 5x5 all the way up to 14x14, and they may have anywhere from 5 to16 colors of flows.

I’ve had Flow Free on my iPhone for years, and it’s saved me fromboredom on many a subway or airplane. From time to time I’vewondered how hard it would be to write a good automated solver for it,but I never took on the project until this summer, when I found myselfwith a few dozen hours of flights on which to occupy myself.

I developed the bulk of my solver over about a week of travel throughIndonesia, Singapore, and Malaysia; when I got back home, I addedabout an order of magnitude’s worth of speed optimizations and someANSI cursor commands to produce animated solutions like the one shownabove. The program also outputs SVG images, which became thebasis for many of the figures in this post.

By the way, I did dig up some prior work on the subject, but I onlystarted looking for it once I had finished my solver. If you’recurious, there’s a list of related efforts at the veryend of this post. As far as I can tell, my solver is the only one I’maware of that can tackle large puzzles (e.g. 12x12 and up) in areasonable amount of time.

From an AI perspective, there are at least two substantially differentways to frame the Flow Free puzzle: the first is as aconstraint satisfaction problem (CSP), and the second is as ashortest path problem. The former is the domain ofSAT solvers and Knuth’s DLX, whereas the latter is thedomain of Dijkstra’s algorithm and A* search.

At first blush, considering Flow Free as a CSP seems like a simplerformulation, because the constraints are so simple to state:

Each free space must be filled in by a color.
Each filled-in cell must be adjacent to exactly two cells of the same color.
Each dot must be adjacent to exactly one filled-in cell of the same color.

In contrast, shortest path algorithms like Dijkstra’s and A* seemill-suited for this problem because the zig-zaggy flows found inpuzzle solutions rarely resemble short, direct paths:

Despite this apparently poor fit, I decided to take the “A*-like”approach for two main reasons:

I spent years in grad school coding up search-based planners with A*.
When you have a hammer, the whole world looks like a nail.

Although finding shortest paths is a generalgraph search problem, my solver operates on atree rooted at the initial puzzle state. Each node in thetree not only stores a puzzle state, but also the current positionof each flow. We can generate a successor for a state – i.e. its“child” in the tree – by extending one of the flows into anempty cell adjacent to its current position.

It’s vitally important to reduce the branching factor – the averagenumber of children per node – as much as possible, because a largerbranching factor means searching exponentially more nodes. Forexample, a tree of branching factor 2 fully built out to depth of 10has a modest 1,023 nodes, but doubling the branching factor to 4 wouldincrease the tree size to 349,525!

So to keep our branching factor small, for any state we will designatea single active color which is permitted to move. Say we are solvinga puzzle with 6 colors. If we allow moves from any flow’s currentposition, a node might have as many as 24 children (6 colors times 4directions of motion per color); however, imposing an active colorreduces the maximum number of children to 4.

Which color should we choose to be active? Probably the mostconstrained one – that is, the color with the fewest possiblemoves. For example, consider the puzzle below, with the colored cellbackgrounds indicating the initial position for each flow. Both blueand cyan have only one valid move available, but green has four:

Hence, we should choose blue or cyan as the active color now, andpostpone moving green until later, in hopes that the board has gottenmore crowded by then. In the board above, we would say that the cyanand blue flows have forced moves because there is only a single freespace next to the current position of each one.

Restricting moves to a deterministically-chosen active color hasanother important side benefit: it prevents duplicate states fromarising in the tree. Otherwise, we could imagine arriving at the samestate via two different “routes” which differ only in the order theflows are created (say moving red-then-green vs. movinggreen-then-red).

Although we could use breadth-first search to solve the puzzle,I found that it’s significantly faster to go withbest-first search instead. The method I ended upusing is kind of a poor man’s A* search in that it computestwo quantities for each state (x):

a cost-to-come (g(x)) that considers all of the moves made toget to this state; and
a cost-to-go estimate (h(x)) that estimates the remaining“distance” to a goal state.

My program defines the cost-to-come (g(x)) by counting up the“action cost” of each move. Each move incurs one unit of cost, withtwo zero-cost exceptions: completing a flow, and forced moves.

The heuristic cost-to-go (h(x)) is simply the number of empty spacesremaining to be filled. In terms of A* search, this is aninadmissible heuristic for my cost functionbecause it disregards the possibility of future zero-cost moves;nevertheless, it works pretty well in practice.

For best-first search, I put the nodes in a heap-basedpriority queue which is keyed on the total cost (f(x) =g(x) + h(x)) for each node (x). As new moves are generated, theyare placed onto the queue; the next one to be dequeued will always bethe one with the minimum (f(x)) value.

As a concrete illustration, consider the tiny puzzle below:

Red has made two moves, but the first was forced, so the totalcost-to-come (g(x)) is 1. There are 8 empty squares remaining, sothe cost-to-go (h(x)) is 8. Hence we see the total cost (f(x) = 8 +1 = 9).

Consider this puzzle state:

Given the moves made by blue, the only way that the free space to theright of the orange flow could get occupied is if orange moves intoit. From this example, we can now say a move is forced:

…if a flow has only one possible free cell to move into (theoriginal definition); or,
…if an empty space is adjacent to a single flow’s currentposition, and it has only one free neighbor.

Flow Free Courtyard Spin Level 1301

Recognizing the second situation is a bit more code-intensive than thefirst, but it’s worth it, because we are always looking for ways toreduce the branching factor. Without considering this type of forcedmove, it might seem like orange has three possibl