Home » .NET » C# » Kami 2 Solver

Kami 2 Solver

I love the game Kami on my iPhone, by State Of Play games. When they brought out the sequel, Kami 2, I was very excited! But it proved to be a lot harder than the original, and before no time I was stuck and had run out of hints. So I wondered if it was possible to solve this puzzle with a program. I’d written myself a solver for Soduku in C# using the algorithms I used in my head to solve the problems. I figured I could do something similar with Kami.

The first solver I found was by Rahul Anand using Python. The source is here:

https://github.com/eternalthinker/kami-solver

He used an A* algorithm and graphs. First you have to identify the different regions of the puzzle to be solved and label them. For me this looked like this:

Marked regions

Once you’ve marked the regions you can then create the regions in code and solve it. For this puzzle it became:

This solved my puzzle. But it was a lot of work to achieve this! I thought it would be easier if I could take a screenshot of the puzzle, upload it into a WPF, use OpenCV to find the regions and their colors, then save that in a JSON file. Having done that I could change the Python solver to upload the JSON file and solve it that way. That was where I started. But things were a little more complicated because the puzzles had triangles and not squares and it was harder to spot the regions using OpenCV. I decided to go for a simpler approach. I would look at the screenshot, work out where the color regions were defined (the bottom right corner of the screenshot). I also knew where each of the triangles were in the screenshot. I could sample the color at the centre of each of these triangles, choose the closest color (based on their euclidian distance), and set the whole triangle to that color.

This was when I came across Roslyn Michelle Cyrus’ post here:

http://www.rozmichelle.com/kami2/

This post was truly inspirational, and very well written. It was based on Reactive, but I used a number of her ideas and implemented them in WPF and C#.

I have added the ability to edit a graph (click on the Edit button). I found that for puzzles that had transparent triangles my algorithm wasn’t too good at spotting them.

I implemented a flood fill algorithm using Roz’s BFS algorithm. Once you have loaded a graph, and if you aren’t in edit mode, you can click on a color and then click on a triangle and it will do a flood fill from there of the selected color. You can click on the reset button to put things back to where they were.

If you hover over any of the triangles it will show you their row and column, together with their color code. Hovering over the color buttons will also give you their color code (handy for working out what the solution text means!).

If you click on “Compress” once you’ve loaded a graph, it will do a color compress of the puzzle into the different regions. You must do this before you can click on the “Solve” button. It will also use GraphViz to visualise the compressed graph.

Download the latest version of GraphViz from here:

https://www.graphviz.org/

My code assumes you’ve installed it to the default Windows location. You can always change the setting in the program if you put it somewhere else.

I implemented the Python solver in C#, so I didn’t need to do any exporting to JSON. Python has very little types, so that code conversion was a bit challenging!

Here’s a screenshot when you load the puzzle:

Load Screenshot

And here’s what happens when you solve it:

Puzzle Solved

I’m in the process of tidying up the source, but you can checkout what I’ve done so far here:

https://github.com/ianormy/Kami2Solver

Please remember I’ve mainly written this for me 🙂 It’s definitely not production quality code!