posted on Mar 9, 2024

How a puzzle game hides a graph problem

A popular puzzle game on the App Store "Kami 2"¹ recently caught my attention. Surprisingly, this game was released 7 years ago in 2017, and it's still got new "daily puzzle"s curated daily.

Introducing Kami 2

The basic idea is to change the color of each segment in an image[^2]. Once two neighboring segments have the same color, the two segments fuse to become one larger segment. The ultimate goal is to fuse all segments to fill the entire screen with one color, within a predetermined quota of color changes.

Let's visualize this using a publicly-shared example from the official Kami 2 product page. I've drawn my own figure to convey the general idea of the puzzle, along with a possible solution to the puzzle. For this puzzle, you are only allowed two color changes. For each color change, you can (1) change the color of any segment and (2) change that segment's color to any other color present in the image.

The starting puzzle has one cyan segment, two orange segments, and two tan segments. I've used black outlines to highlight the segment that undergoes a color change. Here's one possible solution: In step 1, change the center cyan segment to orange. In the step 2, change the center orange segment to tan. We've now colored all segments in the image the same color (tan) in just 2 moves. We've completed this puzzle.

Our goal in this post to formalize an algorithm for solving these puzzles — first by formulating a set of heuristics we can play the game by.

The hidden graph problem (is not helpful)

Let's see how to translate a Kami game into a graph problem.

• How to build the graph: It turns out that every puzzle is a valid graph coloring; each segment is a node, and segments that share an edge on the board share an edge in this graph.
• How each move is represented: Each time we switch colors for a segment, we're changing colors for a node in the graph. Neighboring nodes of the same color are automatically contracted (i.e., merged).

Interestingly, due to this rule, every state in the game is a valid graph coloring. This leads us to a few potential candidates for heuristics: We can consider the most well-connected nodes first, or more specifically, nodes that unify the most nodes of any other color. Let's dive into some examples to understand how this intuition stacks up in reality.

Solvable? At most one more color than moves.

Before solving puzzles more generally, let's look at the puzzle above and its solutions. There are actually two solutions to the puzzle — the left solution is reproduced from above. The right solution is one we haven't seen before.

We can change the center segment from cyan to orange for the first (left) solution. Alternatively, we can change the center segment from cyan to tan for the second (right) solution. To complete the right solution, we then change the outer segment's color from tan to orange.

Just looking at this puzzle, we notice a trend. We initially have 2 moves left and 3 colors on the screen. After one color change, we have 1 move left and 2 colors on the screen. After another color change, we have 0 moves left and 1 color on the screen. Said more generally, if we have $n$ moves left, we can have at most $n+1$ colors on the screen.

We can prove this statement must be true in order for the puzzle to be solvable. We can do this by breaking up the relationship between moves and colors into different categories:

• After $n$ moves, $n$ colors can be changed into an $n+1$th color. By construction, we know there exists a solution for $n$ moves and $n+1$ colors.
• Say we have $k < n+1$ colors. We can change $k-1$ colors into the $k$th color, so there are only $k-1$ colors that need changing to solve the puzzle. We have $k-1$ colors to change but $n > k - 1$ available color changes, so by pigeonhole, at least one color would have an "extra" color change available.
• Say we have $k > n+1$ colors. Assume for contradiction this puzzle is solvable. Again, we have $k-1$ colors that need to be changed into the $k$th color. However, we only have $n < k - 1$ available moves, so by pigeonhole, one move would need to change two colors. This is invalid by definition of a move, so contradiction. As a result, $k > n +1$ colors with $n$ moves is not solvable.

After all this, we've now shown that if there are $n$ moves left, there can be at most $n+1$ colors left in order for the puzzle to be solvable. If you have 4 moves left, make sure there are no more than 5 colors. If you have 1 move left, make sure there are no more than 2 colors.

Heuristic #1. Eliminate colors

So far, we've determined which puzzles are actually solvable e.g., the number of moves needed to complete a puzzle. However, we haven't determined how to make those moves. Let's try to formulate a heuristic based on our observations of the solutions above.

❌ Removes the most segments. This is equivalent to the intuition we developed from the graph formulation: the node that connects the most nodes of any other color. Both solutions reduced 5 to 3 segments in the first step. However, incorrect solutions do the same. For example, if we change the right segment to gold, or the top segment to orange, these moves also result in 3 segments each (illustrated below). Unfortunately, both of those moves result in an unsolvable state — namely, there is only 1 move left but 3 colors left. As a result, segments removed does not distinguish between correct and incorrect moves.

✅ Eliminates the most colors. Most importantly, if you're starting with $n$ moves and $n+1$ colors, each move needs to eliminate a color in order to solve the puzzle. This is a crucial observation for us, in formulating an algorithm.

In the above puzzle, which segment to change colors for is an obvious one. There is only one segment corresponding to cyan, so we clearly change the color for that segment. Luckily for us, either possible color change for cyan also leads to victory. Knowing this, we now have two takeaways:

1. Pick the move that eliminates the most colors. If the puzzle starts with exactly $n$ moves and $n+1$ colors, then we know each move must eliminate a color.
2. If any color belongs to only one segment, pick that segment to change colors for next. This is guaranteed to eliminate a color.

We've now distilled a set of heuristics to lead us to surefire victory — but only for the above puzzle.

Heuristic #2. Unify all segments of a color

Let's try this our heuristics so far on another example in Kami's list of publicly-available puzzles.

Using our heuristics above, we see a singleton — the navy blue segment in the center — and change that segment's color. However, this leads to failure: We start with 3 moves and 4 colors. In the middle figure, we have 2 moves and 3 colors left. On the right, we have 1 move left but still have 3 colors! This is now unsolvable. What happened, and where did our heuristics fail?

Critically, our heuristic doesn't prescribe how to pick a color. Notice that if we'd picked cyan, we would've unified all cyan segments. If we'd picked orange, we would've unified all orange segments. However, we picked tan, and the center segment doesn't connect all tan segments. This brings us to our second heuristic: Unify colors into one segment where possible. Here are our takeaways so far:

1. When there are $n$ moves and $n+1$ colors, eliminate one color per move.
2. Prioritize "singleton" segments i.e., any color with only one segment.
3. Prioritize any move that unifies all segments of a color.

This helps us solve a broader class of problems, but there's still one more challenge: What happens if there are more than $n+1$ moves available?

Takeaways

In short, solving Kami involves following a few heuristics:

1. When there are $n$ moves and $n+1$ colors, eliminate one color per move.
2. Prioritize "singleton" segments i.e., any color with only one segment.
3. Prioritize any move that unifies all segments of a color.

Yes, there is a graph problem hidden in Kami. However, to date, I have yet to understand how this translation is helpful — besides providing a few guesses for heuristics. If you have any ideas, drop me an email or reach out on Twitter!

posted on Mar 9, 2024