What branch of mathematics is relevant to understanding Kami 2 puzzles?

Question

I'm struggling to find an algorithm to reliably solve Kami 2, puzzles (ideally in Python), and wonder what branch of mathematics I should even start with.

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).

I'm guessing this is a simple matter for people who know the right field (graph theory?) but I'm not one of them!

Answer 1

Observe that the shapes of the different coloured regions don't matter; all that matters is which ones are adjacent to which. So you can strip the problem to its essence by reducing the arrangement of regions to a labeled graph: Each vertex represents a contiguous region of a single colour, labeled by that colour. Two vertices are connected by an edge if the corresponding regions are adjacent.

A move consists of two steps:

1. Change the label of a vertex.

2. Contract all adjacent vertices with the same label.

The goal is to reduce the graph to a single vertex.

An obvious greedy strategy is to choose the vertex which has the most adjacent vertices with the same label, for example the tan region at the bottom left which has four adjacent red regions. It is an interesting question whether such a strategy is optimal, or close to optimal. This strategy is not even well-defined: What do you do if there are multiple candidate vertices? For example, the second-last row has a tan vertex with four adjacent red vertices, and a red vertex with four adjacent tan vertices.

Answer 2

If $c$ is the number of colors on the board, this is the $c$-Free-Flood-It problem. The introduction of the paper "Spanning trees and the complexity of flood-filling games" by Meeks and Scott (2013) seems to give a good survey on what is known about the problem. For example, it's known to be NP-Hard for the $n \times n$ grid with $c \geq 3$, and for trees with $c \geq 4$, and it's in P when $c=2$, and also for any $c$ for paths or cycles.