My Flutter Flight – Generate some Puzzle Levels – Part 2

---

In the last post, I implemented a generator to create new levels for my puzzle game. The next step is to check, whether they are actually solvable. After generating a level and before adding it to the results, I need to check its… solvability.

bool isSolvable(Puzzle puzzle) {
    int moves = 0;
    // get moveable tiles
    // create x new nodes by moving each and creating an new puzzle state
    // move ++;
    // repeated until ruby move ends on goal
    return true;
  }

Looks pretty easy if you display it like this.

Solution tree

To get to a possible solution as straight forward as possible and at the same time defining a levels difficulty, I’m going to use a tree structure to take hold of all the possible moves on the field. We’ll see how my computer likes this.
I will collect all the tiles, that can be moved and proceed all movements on a separate edge on my solution tree. The leaves are new puzzle states that are processed the same way, until a solution is reached.

I crashed the app…

At first I wondered why my level solving freezes the app, then I added console output to log the number of leaves I’m handling…

leaves: 1
leaves: 9
leaves: 41
leaves: 118
leaves: 259
leaves: 503
leaves: 944
leaves: 1645
Application finished.

Okay, I reached a critical mass of solution tree size. BUT it technically works. Now back to my education that somehow went missing for a short period of time. That is that there is broad search and depth-first search. And obviously I needed the other type.

Broad Search

This is what I tried first. It gives you the fastest way to solve as soon as possible. … as long as your machine can handle it, what mine obviously can’t. That does not mean that this is per se a bad approach.

If there is a limited number of possible moves for each state, broad search is perfectly suited. Just define a maximum depth to stop and when no solution is reached by this point, you declare the level unsolvable.

Depth-First Search

This approach follows one random list of movement until the maximum depth is reached. If there is no solution, go one step back and try one of the other. Then work your way back up to the root. You won’t stop when solving the level, but keeping the solutions depth as your new maximum depth to find a better solution.

This still takes an eternity, even for 4×4 levels, but at least my computer didn’t gave up on that, although he couldn’t finish calculating.
Nonetheless I need a more efficient way when I want to tackle larger levels. So I need to make my search for a solution more efficient. And searching in a tree is not the answer to my problem.

NP complete

Turns out my problem is officially non-solvable this way. It takes ages to solve a random puzzle on a small field. This is no solution for me. I want to go up to 16 x 16…
So there will be a part 3 after all. I will have to do a lot more work by hand and with my own brain.

Although this doesn’t work for me, it might still be helpful for some of you. And I got a random puzzle generator plus the rules implemented. That’s worth something.