8
$\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).

Improve this question
$\endgroup$
1

4 Answers 4

Reset to default
5
$\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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ F# though! Haskell would be perfect! $\endgroup$
    – orome
    Jun 10, 2017 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$
    – Brian Berns
    Jun 10, 2017 at 18:28
  • 1
    $\begingroup$ No worries. I just wish it were in something I'm set up for (Python, Haskell, Mathematica). $\endgroup$
    – orome
    Jun 10, 2017 at 18:52
2
$\begingroup$

I coded up an A*-based algorithm that solves Kami2 levels. It's described in my blog post here (with the C++ code). I'm sure there are ways to improve it; would love to hear ideas.

Improve this answer
$\endgroup$
1
$\begingroup$

I have written a backtracking algorithm based on Constraint Satisfaction to prune the search space. Here is the link on GitHub solution Though it does not use image processing to create the graph it works well on the puzzles I was trying to solve. Maybe can add it during the summer

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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