Mora Jai Box Solution Space Analysis

Introduction

This post is a work in progress.

Mora Jai boxes are simple-looking puzzles that can be configured into a huge variety of challenges. The original set of puzzles from Blue Prince mostly have short, simple solutions, but lengthy and difficult solutions can be constructed by exploring deeper state spaces of the tile grid.

Initially, I wanted to create a list of the most difficult configurations by cataloging the longest solutions, but it turns out that length is not the best predictor of difficulty. Many of the longest solutions rely on repetitive patterns rather than complex logic and novel mechanics.

Ultimately, the list of Challenge puzzles in my simulator was found using a combination of brute-force search, automated filtering, and manual inspection.

Definitions

• Colors - See this color chart
• Tile - One of 9 inner colored tiles
• Outer Button - One of 4 round colored buttons

• State - The color configuration of the outer buttons and tiles
• Depth - The minimum number of moves required to solve a given state
• Solvable State - An initial configuration that can be solved using the correct sequence of tile presses
• Solved State - A state where the colors of the 4 corner tiles match their corresponding outer buttons

• Box - A Mora Jai puzzle with a specific outer button configuration
• Symmetry - A transformation that can be applied to a box to produce a box with an equivalent solution

Solution Space

The Mora Jai Box solution space is large, but still analyzable using optimized brute-force algorithms.

There are 10,000 (10⁴) possible outer button configurations (“boxes”), and each of these has a unique solution space.

For each outer button configuration, there are 1 billion (10⁹) possible ways to set the inner tiles.

The inner tile presses could be mapped out completely for efficient searching using a directed graph, but this graph would take up a huge chunk of memory that exceeded any RAM that I had available. Instead, I opted for an iterative approach on one box at a time, where each solved state is marked as depth “0”, then any state that can produce depth 0 is marked as depth 1, and so on. The state tracking array only requires 1GB of RAM. Without optimizations, the algorithm needs to iterate N times over 1 billion states, where N is the depth of the longest solution.

Unsolvable States

Many inner tile configurations cannot possibly lead to a solution. For instance, if one of the outer buttons is pink, but there are no pink tiles present in the puzzle, then the puzzle cannot be solved with any combination of tile presses. To speed up the analysis, we can filter out these unsolvable states.

In puzzles whose outer buttons consist of “simpler” colors (pink, green, yellow, violet), the state space can be initially reduced by over 90%. For the most complicated arrangements, the benefits shrink to 25%–50%.

Symmetries

One might expect large overlaps in the solution space due to some key symmetries in the tile behaviors:

• Vertical symmetry: Black shifts its row right.
• 180° symmetry: Pink rotates surrounding tiles clockwise.
• Vertical or 180° symmetry: Violet (south movement) mirrors yellow (north movement).

For example, these two configurations at depth 57 exhibit vertical symmetry with each other.

For a majority of cases, exchanging yellow with violet and vertically mirroring the outer button configuration produces nearly identical outcomes in the distribution graph. This plot shows the solution depths for the box with four yellow outer buttons, versus the box with four violet outer buttons:

The yellow and violet boxes both have a total of 64,492,718 solvable states, but looking closely (zoom in on depth 7-12), the state distribution is skewed slightly in the first half of the graph. Symmetry is broken whenever black and pink tiles co-exist in the same puzzle, and the varying solution lengths affect the shape of the graph. Deeper states tend to lack pink tiles, so the yellow & violet graphs converge after depth 30.

I did not make any assumptions about symmetry in my analysis due to the clear divergence that occurs at certain depths.

Implementation Details

The final depth analysis algorithm executes in three stages:

• Pruning (CPU): Using quick logical deduction, unsolvable (“dead”) states are eliminated from a box’s state space.
• Iteration (GPU or CPU): One depth at a time, beginning with the solved 0 state, the remaining states are submitted to an OpenCL kernel that simulates the puzzle’s button presses and marks the next depth. The GPU code is at least 10× faster than the CPU code.
• Backtracking (CPU): States that are part of a deeper state’s solution path are marked to be ignored in the detailed output. This step isn’t perfect since it doesn’t consider multiple solution paths of the same length, but it increases the quality of data and makes manual review easier.

Multiple instances of the algorithm run in parallel, pulling work from a randomized queue of boxes to help distribute the CPU and GPU loads.

The source is available at https://github.com/cjgriscom/MoraJaiAnalysis.

Results

The program took 3 days to compute the state distribution for every box. It also cataloged the tile configurations for any depth with fewer than 2,000 states for manual inspection.

State Counts

Roughly ~10.45% of Mora Jai configurations are solvable. Below is the high level distribution breakdown, considering all 10,000 boxes.

Depth Extrema

Below is the isolated data for the most extreme outer button configurations.

Lowest solution depth	13	and
Highest solution depth	84	and
Fewest solvable states	20,266,135	and
Most solvable states	383,935,071

Solution Tropes

This section is not finished yet