The other day I was bored so I did what everyone do when they’re bored: I went for my phone and searched for a new game. I found this game, Kami 2. It’s a very relaxing and pleasant puzzle game and I finished quite a few levels. But, like every game of this style, the levels were getting harder and it can give you clues but for a price. So I thought what everyone think at this time but nobody say: how can I cheat?

Today I show you a way to have a little “extra help” with this game, it’s something similar to what a did in a previous post with a game called Hitori and the idea can be still extended to other games.

The Game

First of all, a video may be better than any explanation I could give.

I present you the particular level I’ll be using throughout the post.

subte Our test case

The objective of the game is to paint each cell to end up with only one color at the end

kami_fin1 Starting state kami_fin2 Solved state

To do this we tap a color from the bottom of the screen and then any cell. That cell and every other adjacent cell with the same color will be painted with the new color we chose

kami_color1 Tapping with a color kami_color2 One color changed

You have to do this in less than X movements and that’s it, those are the rules.

The Idea

I want to solve this automatically, so, what can I do?

One naive solution would be a program that tries every color in every cell until it reaches a solution. Well… if it works, it works, let’s go with that.

It would be very slow if I make a program that really taps on the screen and really plays the game, so I’ll have a representation of the game and have a python script to solve it.

Having group of cells adjacent to each other seems like a graph, in particular we can abstract our level to:

subte Simplified graph representation

If we can give to the python script this representation, it can solve it trying every possibility like we said before.

To reach that point we need to:

  • Capture a snapshot of the level
  • Identify each cell and which neighbours it has (making a graph)
  • Identify each cell color
  • Use backtracking to solve that graph and reach a solution

The Solution

For this script and all image processing I’m using the image library pillow.

To start I just took a screenshot of the level with my phone. I could have automated this first step, but I'll leave it for the future.

Our test case again, the screeshot I took

To be able to recognize each cell's color, first I have to know where each cell is. This can be done easily with a couple of for loops and calculating correctly the separation between each cell.

Every cell recognized

In this step I can also start making the graph, it is straightforward to do this.

Every cell connected in a graph

Then I read each color from the bottom of the screen and the color of each cell. I can't compare them directly because the colors aren't uniform, so I took an average from the surrouding pixels and took the closest matching color. This worked flawlessly.

The colors recognized

Ok, from this representation we can already solve it. Only theoretically. The problem is that we have way too many nodes and we’re using backtracking, this will not finish in a reasonable time (it doesn’t, I tried).

We can give it another go. It’s really the same if I tap a cell from a sector or other cell from the same sector, so we can group or ‘clusterize’ our graph.

Having a clusterized version of the graph means that now we have only one node per cluster instead that one node per cell. We've reduced the number of nodes drastically.

Each cluster recognized separately

Now our backtracking algorithm can finish in our lifespan and it gives us the solution for the puzzle! (magic!). You can click the image to see better the solution. Each number represents the order in which to click (strating from zero) and which color to choose

The solution to this puzzle

The Next Steps

Ok, so we have a working script that solves this puzzle. The manual labor consists in taking a screenshot of the level and running the script. Here are a couple more of solutions:

kami_sols1 Another solution kami_sols2 This one was hard...

So it is solved. Only theoretically… again. I had to keep the script running all night for that last gray and yellow puzzle. Backtracking isn’t the real anwser here. In the future it could be cool if I change the solver from backtracking to something a bit more smart like A* and integrate everything to android.

The code for this script can be found here

Oh well, meanwhile I’ll try not to cheat anymore and enjoy the game (and you should too, it’s very good!).

That’s all, thanks for reading!