I've created a small mathematical puzzle involving a 6x6 grid, which has been randomly colored with four distinct colors. The objective is to reassign colors with the fewest changes possible, ensuring that each color forms a connected region.
Here's my question: What is the smallest value of $k$ for which every instance of this problem has a solution that requires no more than $k$ color alterations? If feasible, please provide a constructive proof.
Here is the game: https://convex.red
Firstly: What a nice question! I like that you've implemented this to be able to play around with!
Now this isn't a full answer, but it's a bit too long for a comment, so I'm posting it as an answer.
My intuition says that the "most difficult" board is the one where the total distance between all the colors is maximal. Namely let $A_{6\times6}$ represent the board, with elements $A_{ij} \in \{R,G,B,Y\}$ (red, green, blue, yellow).
Then given a pair of indices $(i,j)$, with $A_{ij}$ being currently color $c$, let
$$\delta(i,j) = \text{Metropolis distance to the closest cell that is also color } c$$
Then the total distance of a single color $c$ is
$$D_c = \sum_{(i,j): A_{ij} \text{ is color } c} \delta(i,j)$$
And the total distance between all colors is
$$D = D_{R} + D_{G} + D_{B} + D_{Y}$$
My guess is the board for which $D$ is maximal is the "most difficult" board, or the board that takes the most steps to solve.
If that's true, it's not too difficult to see that the board on the left takes on this maximum (or any of the $4!$ boards that permute the colors of the board), it seems that it needs $16$ steps to solve (around half of the squares would need to change color, except for the green and yellow corners).
I might be wrong though, but my guess is that the answer is $16$, but obviously this would need a rigorous proof.
Edit: Originally I thought it would take $18$ steps to solve the above board, now I've changed it to $16$ due to Gilad's comment. Thank you for the correction!