Zhed Solver

Table of Contents
  1. Background
  2. Algorithms
    1. Uninformed Search
    2. Basic Heuristics
    3. Reverse Path Algorithm
    4. A* Algorithm
  3. Using the Solver
  4. Download

Click here to go to the Zhed solver.

Background

One of my computer science courses briefly went over state space search algorithms and how they can be used to solve problems without knowing the solution. I found the topic fascinating, and wanting to put my skills to the test, tried to create my own state space search algorithm from scratch using what we learned in class.

I ended up making a state space search algorithm for solving puzzles from the mobile game Zhed, made by Ground Control Studios. The puzzles are grids with numbered cells and a goal cell (the white square). To complete each level, each numbered cell must be expanded in one of four directions and overlapped to reach the goal cell. Each cell expands n cells in the direction chosen, decreasing by one for each empty cell. When a expanding cell overlaps an already filled cell, the number of cells to be filled in the direction of the expansion is not decreased.

Figure 1b: Solving level 12.

Figure 1b: Solving level 12.

I expected this project to only take around a week, including the uninformed and heuristic-based search algorithms, but ended up working a little over a month trying to get it to be as good as possible. I went through multiple algorithms, trying to find the best one for the job. At first, the process was fun, but after that one month mark I started to get a little frustrated with the solver and the exponentially increasing time required to solve the later levels.

The aim of this state space search solver was to solve all 100 levels in Zhed, but efforts slowed to a pace that would make a snail proud of its speed. The solver made it to level 68 before it couldn't take it anymore, skipping only a handfull of levels between that had to be solved manually.

As of writing this article, this project is not yet finished. I am taking a break from it, and may return better prepared to improve the algorithm later on. This article describes the process of creating the state space search algorithm from birth to its current state.

Algorithms

The first plan of action for the Zhed solver was to create an uninformed search algorithm that would essentially try every combination of valid actions until it solved the level. If my math is correct, the formula for calculating the size of the state space is: \[ N\left(n\right) = \sum_{i=1}^{n} \left( 4^i \frac{n!}{ (n - i) ! } \right) \]

Explained: the summation of selecting 1 to n cells, where each cell has 4 directions (\( 4^i \)), times the number of permutations of the i selected cells (\( \frac{n!}{ (n - i) ! } \)). For five cells, N(5) = 157,780, while for eight cells, N(8) = 3,392,923,552.

The uninformed search algorithm worked for the first twenty/thirty levels before things started breaking exponentially. Memory would be exhausted quite quickly as new states were added to the list, and on a few occassions I had to restart my computer because I wasn't able to stop the solver in time and the computer became unusable since the solver would eat up all the memory (8 GB!) within a few minutes.

Basic Heuristics

The next step of writing the algorithm was to implement some basic heuristics. The first, and most important, heuristic I found was to assign higher priority to cells farther away from the goal cell. This was able to more than halve the number of states that had to be checked before finding a solution compared to the uninformed search statistics. Other heuristics involved skipping expansion in a direction with no cells and saving the cell in front of the goal for last.

And yet, it still wasn't enough to find solutions quickly. This approach managed to get to level 42 (with 18 cells!) before running out of memory. Thus began the hunt for a new algorithm entirely.

Reverse Path Algorithm

The Algorithm

I ended up creating an algorithm I called the "reverse path algorithm" since it does exactly what the name implies.

The algorithm starts at a goalfront cell (a cell that can expand directly towards the goal cell) and builds a tree of interacting cells (cells that could be expanded into the path of their parent cell to help the parent expand farther). The algorithm recursively adds interacting cells to each cell node, as long as the node being added isn't found up the tree, creating a unique reverse path of cells.

Once no more cell nodes are added to the tree, then the state space search algorithm starts at the leaves of the tree and travels upwards, expanding nodes as it goes until it reaches the root. If the goal is reached, then the solution is found, otherwise the search algorithm will move onto the next leaf and try again. Note that multiple goalfront cells will require multiple trees.

The next issue I had to tackle was what I called multicell, where more than one interacting cell is used to help expand the parent. Handling multicell situations required doing permutations (on top of permutations). When adding a node to the tree, I would also add permutations of entire branches of the interacting cells and add each leaf of those permuted branches to the recursive process of creating the tree. This is why the algorithm didn't go very far when there were more than a handful of cells.

It's interesting to note that this algorithm found a second solution to level 21, different than the one I used to solve it manually.

A* Algorithm

After some more thought, I realized that I could use a modified version of the A* algorithm to find best paths. By starting from the end and looking for any cells that could reach it, with the help of other cells recursively, I could find the solution much faster by going backwards instead of forwards. This led to another rewrite of the solver algorithm.

The Algorithm

The algorithm uses this formula for determining priority: \( f(s) = g(s) + h(s) + i(s) \) where \( g(s) \) is the cost to reach the state (the number of cells expanded), \( h(s) \) is the heuristic of how many open cells are left to fill, and \( i(s) \) is the cell-based heuristic value.

The way this algorithm works is it starts at the goalfront cell and gets a list of all the interacting cells. Using level 12 (Figure 1a.), the algorithm would start at 3 (1, 7) and get the interacting cells 5 (2, 2), 4 (5, 2), and 1 (3, 5). If we assign letters to each cell, ordered from top-left to bottom-right, we get:

The e cell can immediately be removed from consideration because its open distance, the distance between the cell and its parent minus the possible filled cells between, is \( 2 - 1 = 1 \). In other words, e can never be expanded towards f and reach to help it expand into the goal.

a is given a higher priority because it is closer, which statistically leads to the solution faster. We can use the numbers 0, 1, 2, 3 to represent expanding up, left, down, and right. Now we can create a priority queue, which will look like this when traversed: \( f_1 a_2 \), \( f_1 b_2 \).

We then continue the pattern by getting the interacting cells from the last cell added to the first. Examining \( f_1 a_2 \), we then get: \( f_1 a_2 c_1 \), \( f_1 a_2 d_1 \), \( f_1 a_2 e_0 \), \( f_1 a_2 b_2 \).

This continues until the solution is found, which is the sequence \( f_1 b_2 c_1 e_0 d_1 a_2 \). Each state is generated at runtime since all the sequences are checked in reverse order.

Results

This approach was magnitudes better than the previous algorithms I had written, where it solved the first 40 levels in a total of 37,000 actions done. Level 29, which took 5 million state checks in the reverse path algorithm, was optimized down to only 18,000 actions with the A* algorithm.

The memory consumption was also much better than the previous approaches, where most levels consumed less than 1 GB.

Unfortunately, some levels were still out of the algorithm's grasp. Level 42 did 51 million actions in 46 minutes before I stopped it, while level 47 did 125 million actions in under two hours and still couldn't find a solution. The worst result was in level 64, which actually began running out of memory within 12 minutes after doing 25 million actions. The last level it solved was level 67, with nearly 7 million actions done.

Clearly, the algorithm still needs work, but for now I've run out of ideas and will be shelving this project for a while.

Using the Solver

To use the Zhed Solver, fill in the numbered cells in the grid according to the level, with the goal marked as -1. Cells set to -2 are considered filled in, but not active. To change the size of the grid, change the height and width boxes and press Build New, which will create a new grid to the specified size.

Zhed Solver with the cells from level 12 filled in.

Zhed Solver with the cells from level 12 filled in.

Once ready, press the solve button. The actions counter will increment, showing how many actions are being done. When the solution is found, the solver will output a step-by-step walkthrough of how to solve the level.

The steps to solve level 12 appear below.

The steps to solve level 12 appear below.

Note that if you choose a complicated level, your computer may run out of memory! Be cautious and watch your memory usage for very complex levels.

Pressing Get URL Shortcut will create a URL with the current grid state so you can go to saved states without having to enter them in manually. This URL will send you to the solver with level 12 already filled in.

Download

You can download a local, browser-run version with the source code from GitHub here.