7
$\begingroup$

I'm finding my life has been consumed by Kami 2, partly because I seem to have achieved some "insight" and am able to solve the puzzles reliably, almost always on the first try.

The rules are simple: Each move consists of replacing any one contiguous colored region with one of the available colors (from a palette provided). The goal is to have filled the entire image with a single such color in a given number of moves (indicated in the toolbar).

But whatever this "insight" is, it's not enlightenment. I don't know why or how I'm doing it, I just am.

I wonder if there is some simple algorithm for solving these puzzles reliably (involving, I assume, some underlying graph theory).

$\endgroup$
4
$\begingroup$

Flood-filling games are, for sufficiently many colours, NP-hard. There's no known algorithm that's significantly more efficient than brute force with pruning.

$\endgroup$
2
$\begingroup$

I implemented an algorithm here that can solve some Kami 2 puzzles quickly. (Specifically, those where the number of available moves is not much higher than the number of colors in the palette.) It's a brute force approach with a few simple heuristics. I think it would be very difficult to design an algorithm that approaches these problems in a human-like way, but perhaps a neural network of some sort could be trained to do it.

$\endgroup$
  • $\begingroup$ F# though! Haskell would be perfect! $\endgroup$ – orome Jun 10 '17 at 15:53
  • $\begingroup$ I wouldn't know how to do the image manipulation in Haskell, and some of the performance optimizations are not purely functional. I could translate it to C# if you'd like. $\endgroup$ – brianberns Jun 10 '17 at 18:28
  • $\begingroup$ No worries. I just wish it were in something I'm set up for (Python, Haskell, Mathematica). $\endgroup$ – orome Jun 10 '17 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.