Kami is Graph Contraction

A while back I downloaded an iOS game called KAMI 2. It’s a fun, relaxing puzzler with many nice touches — a very well-crafted app. Playing the game looks like this:

IMG_2978

The goal is to get the screen to show just one color (any color) using a limited number of moves. Each move changes a connected region’s color. In the screenshot above, there are 8 moves left.

What I realized, eventually, is that the core mechanic is graph manipulation. Each solid region is a node with an associated color. Edges connect adjacent regions. Changing a region’s color corresponds to changing the associated vertex’s color, followed by edge contractions to eliminate adjacent nodes with the same color. A monochromatic screen corresponds to a singleton graph.

It turns out that the general problem of deciding whether you can turn one graph into another one via edge contractions is NP-hard. However, that doesn’t directly apply to KAMI, since the singleton graph is a trivial target, and we’re furthermore interested in limiting the number of moves made.

I hacked up a Python script using OpenCV to generate graphs from screenshots of KAMI:

 

For most of the early (easy) boards, you can simply find the node that connects to the largest number of other-colored regions. But the graph above is a counterexample to the greedy application of that rule: the upper-left black patch connects to four red regions, and the 2nd biggest black patch connects five white triangles, whereas the correct move is to connect the two big green triangles via the beige node.

I’m pretty sure that random selection of nodes to contract (and colors to contract with) yields exponential running time. Needless to say, exhaustive search is infeasible. I haven’t yet come up with a good heuristic to guide the search process in balancing between greedy exploration and minima-avoidance. I expect that a traditional optimization algorithm like simulated annealing or hill climbing would be very effective with a bit of tuning, but I’d prefer a non-randomized approach.

Even though I haven’t yet cracked this nut, I thought the problem was pretty enough to write up!

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s