Chris Smith in Gaming

Kami 2 Solver in F# - Part 1

This post covers a Kami 2 puzzle solver I wrote in F#. If you haven’t played Kami 2, or its predecasor, I would urge you to check it out on the App Store.

Kami offers beautiful aesthetic, high production value, and wonderful “daily puzzles” feature. But ultimately, it’s fun because of a simple mechanic that requires just the right amount of experimentation to find the solution.

Anyways, a lot of Kami playing goes on at my house. Things were going great until I got stuck on the last few levels.

The game’s makers sell puzzle hints via IAP. So I could just spend a few bucks to get unblocked… but that didn’t seem nearly as much fun as writing my own Kami 2 puzzle solver in F#!

Project Overview

Once you have distilled the puzzle into a colored graph, solving it is actually straightforward. The hard part is actually encoding the puzzle itself.

Solving puzzles and various optimizations will be covered in a future post. For now, I’ll cover the work required to get data.

If I wrote a fancy UI using WinForms or AngularJS, inputting puzzles manually would be error-prone and time intensive. So I needed to automate it.

I could have jailbroken my phone and try to reverse engineer data files. (I guess?) But instead my solver works by just analyzing screen shots from the game. Using some heuristics and a little bit of math, you can reliably extract the puzzle configuration.

Image Processing on .NET Core

The first step was probably the hardest one: how do you read/write images in .NET Core?

On Windows, you would just use System.Drawing and call it a day. However, as pointed out earlier this year dealing with images on .NET Core is a trecherous endeavor.

After a couple of false stats trying other libraries, I went with SkiaSharp. Which as an added bonus has some great documentation.

The library is a bit more onerous to work with than System.Drawing, but once you get the hang of the SKSurface/SKCanvas/SKPaint relationship, everything is pretty straightforward.

Puzzle Extraction

If you just want to go straight to the code, check it out on GitHub at: chrsmith/kami2-solver. Please poke around and let me know what you think. I’ll go over the more interesting bits here.

Debugging Image

Debugging is hard. Especially with lots of image data.

So rather than writing cumbersome unit tests or logging hooks, I opted create annotated copies of the input images. This allowed me to overlay information and visually check if things were OK. (Of course if this were more than a fun weekend project, both unit tests and logging hooks are always a good investment.)

As for the code, there is nothing out of the ordinary. The only wart is that in F# you cannot use the use keyword inside of a primary constructor. (Since the F# compiler has no idea when to actually call Dispose on those objects.)

// Kami2 puzzle image with annotations to aid in debugging.
type AnalysisDebugImage(originalImage : SKBitmap) =
    let surface = SKSurface.Create(originalImage.Width,
    let canvas = surface.Canvas
    let paint = new SKPaint(TextSize = 80.0f,
                            IsAntialias = true,
                            Color = kBlack,
                            StrokeWidth = 5.0f)

    do canvas.DrawBitmap(originalImage, 0.0f, 0.0f, paint)

    member this.DrawLine(x0, y0, x1, y1, color) =
        paint.Color <- color
        canvas.DrawLine(x0, y0, x1, y1, paint)

    member this.AddCircle(x, y, color) =
        paint.IsStroke <- false
        paint.Color <- color
            x, y, kAnnotationSize,

    member this.AddCircleOutline(x, y, color) =
        paint.IsStroke <- true
        paint.Color <- color
            x, y, kAnnotationSize,

    // Save the image to disk in the PNG format.
    member this.Save(filePath) =
        let finalImage = surface.Snapshot()
        use pngEncodedFile = finalImage.Encode();
        File.WriteAllBytes(filePath, pngEncodedFile.ToArray())

    // Clean up Skia objects.
    interface IDisposable with
        member __.Dispose() =

After sprinkling a few calls to DrawLine, AddCircle, and AddCircleOutline in the analysis code, you can see beautiful results like the following. (I’ll explain what the colors and redudnant circles are all about later.)

analyzed puzzle

Color Matching via Linear Algebra

You might notice that the colors aren’t solid, and feature subtle variations with shading. While this makes things more aesthetically pleasing, it also makes comparing pixel data more challenging.

Fortunately a little math can solve this problem for us. (“Maths” if you are in the UK, for some odd reason.)

First, I don’t look at a single pixel when determing a color. Rather I compute at the average of a larger block of nearby pixels. This reduces the impact of these subtle color variations.

Second, because of the averaging done, you cannot just rely on a basic comparision to see if two colors are equal. Instead, you need a way to measure the “closeness” of two colors.

Measuring the closeness of two data points is a well-known problem, and the solution is to compute the dot product (wikipedia). Don’t let all the funky symbols scare you! It’s really a simple concept.

For normalized vectors (length of one), the dot product is the cosine of the angle between the vectors. So if they are identical (pointing the same direction), then the dot product is 1.0. If they are orthogonal/ perpendicular, the dot product is 0.0. If two vectors were going in completely different directions, i.e. 180° from each other, then the dot product would be -1.0.

Of course a typical RBG color value isn’t a vector in the traditional sense, but if squint a little, you can think of the RGB value as a vector in three- dimensional space. (Or, four-dimensional if you factor in an alpha channel.)

// Computes the dot product of the two colors as if they were
// normalized vectors.
let dotProduct colorA colorB =
    let colorToNormVec (c : SKColor) =
        let valueArray =
            [| c.Red; c.Green; c.Blue; c.Alpha |]
            |> float
        let w, x, y, z = (valueArray.[0], valueArray.[1], valueArray.[2], valueArray.[3])
        let length = Math.Sqrt(w * w + x * x + y * y + z * z) (fun x -> (float x) / length) valueArray
    let vecA = colorToNormVec colorA
    let vecB = colorToNormVec colorB    
    Array.fold2 (fun acc x y -> acc + x * y) 0.0 vecA vecB

You’ll see this dotProduct function come up in a few places in the code.

Puzzle Colors

Each Kami puzzle has a set of two to five colors that you can use, displayed in the bottom right of the screen.

The heuristic I use to figure out the number of colors the puzzle has is to assume the puzzle has five colors, and then check if any are duplicated. If so, then reduce the number of colors and try again.

This actually works pretty well. You can see why this works when you look at the debugging image below.

The top part shows the original color swatches. The bottom part shows the “probing” done to whiddle down the number of colors. Note that in the cases where it guesses five of four colors, duplicates are found.

identifying colors

Triangle Colors

Once the puzzle’s colors have been determined, next is mapping each individual triangle to a color. This is done by getting the average color of the triangle and checking its dot product against the set of puzzle colors. The highest resulting dot product is the closest match.

However, in the case that no good match is found, e.g. dot product value less than 0.75, we assume the triangle isn’t part of the puzzle. And instead is just showing the “background”.

Converting Raw Data into a Graph

The final stage of puzzle extraction is converting our messy color and color-indexed based data into a graph abstraction.

To define the terms used, each contiguous set of triangles sharing the same color is called a region. Each region has a unique ID and color associated with it, along with a list of zero or more adjacent regions.

// Raw puzzle extracted from a screenshot.
type RawKami2Puzzle = {
    // Number of colors used in the puzzle.
    NumColors: int
    // Index of the color of each individual triagle. See other comments for
    // translating coordinates to triangles, and adjacency rules.
    // Has value of -1 if the triangle doesn't match any puzzle colors.
    Triangles: int[,]

// Kami2 puzzle represented as a graph.
type Region = {
    ID: int
    Color: int
    // IDs of adjacent regions
    AdjacentRegions: HashSet<int>

type Kami2Puzzle = {
    NumColors: int
    Regions: List<Region>


We start with a 2D integer array of triangle colors (each integer corresponds to the index of the puzzle color, or -1 if the triangle is not part of the puzzle.)

First, we construct a parallel 2D array of Region option objects. This allows for quick lookup to see if a given triangle is associated with a region or not. As we flesh out the regions of the puzzle, we’ll keep this array up to date.

    let triangleRegions : Region option[,] = Array2D.zeroCreate 10 29

To start breaking the puzzle into regions, we pick the first triangle not already associated with a region (Option.isNone triangleRegions.[c, r]).

We then create a new Region object to identify that uncharted region, and then flood fill all identically-colored and adjacent triangles.

While walking through the region being flood-filled’s neighbors, if any of them are associated with a different region, then we update both regions to add the “borders” association. i.e. region X borders region Y and vice versa.

Hopefully that was an adaquate description. If not, I’m happy to clarify anything that doesn’t make sense. And the good news is that it fits into less than 50 lines of F# code:

    let rec floodFillRegion col row (region : Region) =
        match triangleRegions.[col, row] with
        // If the triangle's neighbor is already known, mark as neighbor and stop.
        | Some(adjacentRegion) ->
        // If the adjacent triangle does not have a region, then we merge it
        // into the region being flood filled if it has the same color,
        // otherwise we ignore it. (And will get to it later.)
        | None ->
            let triangleColor = rawData.Triangles.[col, row]
            if triangleColor = region.Color then
                triangleRegions.[col, row] <- Some(region)

                // Mark it on the debug image.
                let x, y = getTrianglePoint col row
                let regionColor = solidColors.[region.ID % solidColors.Length]
                debugImage.AddCircleOutline(x, y, regionColor)

                // Recurse
                getAdjacentTriangles col row
                |> Seq.iter (fun (col', row') -> floodFillRegion col' row' region)
                // Ignore the diff colored neighbor, as it will be a part
                // of a different region constructed later.

    // Check each triangle and ensure it is apart of a region.
    for col = 0 to 9 do
        for row = 0 to 28 do
            let triangleColor = rawData.Triangles.[col, row]
            match triangleRegions.[col, row] with
            // Ignore triangles already associated with a region or
            // not part of the puzzle.
            | Some(_) -> ()
            | _ when triangleColor = -1 -> ()
            | None ->
                let newRegion = {
                    ID = knownRegions.Count
                    Color = triangleColor
                    AdjacentRegions = new HashSet<int>()
                floodFillRegion col row newRegion

That’s it! And one nice thing is that while we are building up the regions, we mark each triangle with a determinsitic color based on the region’s ID. So you can see by the colors of the circles where regions begin/end.

marked regions

Next steps

Now that we can extract a Kami 2 puzzle from a screen shot, the next step is to actually write the solver, which takes our Kami2Puzzle puzzle objects as input and outputs something useful to humans.

Check back later for Kami 2 Solver in F# - Part 2.