Note: This is an article from my old dev blog. External links have been updated, but the text is otherwise reposted verbatim.
A couple of weeks ago I discovered a nice little puzzle game called KAMI, by State of Play Games.
The premise of the game is simple: you have a 10x16 grid of coloured tiles, and the aim is to make the board a solid colour by using a limited number of flood fill operations. If you use exactly the move limit then your solution is graded as “perfect”, if you use one more then you’re graded as “ok”, any more than that and you “fail”.
As a gamer, I was intrigued and played it for a few levels. It ramps up in difficulty pretty quickly, and I found myself stuck after a short while. Then my programmer brain set in, and I thought to myself, “I bet I could code a solver for this”.
So I did. Here’s how I did it.
My first thought was “well, try every permutation of target tiles and colours in order, up to the move limit”. Essentially a complete depth-first-search of the move tree. After some quick mental math (160 tiles, 3-5 colours, 3-9 moves = stupidly big numbers) I figured that was a terrible idea. I still wanted to traverse the move tree, but I figured some significant pruning was needed.
Firstly, we can consider the board as a collection of regions, rather than a grid of tiles. Since a flood fill on any tile within a given region will give the same result, this reduces complexity significantly. The first level (pictured below) is reduced from 160 tiles to 2 regions, already a vast improvement.
The next decision I made was to ignore “illegal” moves. The game doesn’t let you fill a region with the colour it already is (since it wouldn’t alter the state of the board). Thus, when trying region/colour combinations, we can omit pairings where the colour already matches that of the region.
After that, I decided to go for logical pruning. This comes in two forms.
First, I only try colours that are still in play on the game board. Any colours in the “palette” but not in play on the board are ignored. The logic behind this is as follows:
Every move, you want to join regions together to reduce the entropy of the board - the winning state being a lone region in play. Playing a colour that is no longer in play does nothing to reduce the board’s entropy, as it cannot join existing regions together.
Second, I take the number of remaining moves into account. Take the image below as an example. There are 3 colours on the board, but only 1 move remaining. Since a single move can remove at most one colour from play, it’s impossible to solve this board in one move. Similarly, a board with 4 colours and 2 remaining moves also cannot be solved. So if movesRemaining < coloursInPlay - 1, there’s no point traversing further down the move tree, since no leaf node can possibly contain a solution.
As one last act of pruning, I wrote my solver to return the first valid solution, rather than fully traverse the tree and collect all valid solutions.
Another trick I used was to sort the regions in descending order of area, so it would try the larger regions first. This is slightly beneficial for most puzzles, but there are a select few where this is actively unhelpful. Level D9, pictured, starts on a single-tile region, and I’ve yet to see how long my solver takes to figure that out.
So there you have it. My solver is remaining closed-source until further notice. The implementation details are a little bit hacky and untidy, and I’d like to do it over again from scratch with a clearer plan in my head.
I hope you found this interesting :)