18
$\begingroup$

[ Question based on the sock dye game ]

[ Update: It appears that this game is better known as "Flood it" and is NP-hard. Also, "the number of moves required to flood the whole board is $\Omega(n)$ with high probability." ]

Question: How many color changes (= moves) are needed to complete a $n\times n$ game of $c$ colors? That is:

  1. What is the expected number of minimum moves needed?
  2. What is the maximum number of moves needed?

Is there a strategy that always solves the game with minimum moves?*

Description of the game

Given an $n\times m$ grid where each node is painted with a random color between $c$ possible colors, we define a cluster ("our" cluster) of neighboring nodes that contains only nodes of the same color and must include the upper left node.

Grid of the game

We can change the color of our cluster at will, thus extending it. The goal is to expand our cluster to all the grid.

* Where is the proper place to ask this?

  • 1
    Also please suggest a better title.2011-04-21
  • 0
    You've got $c$ colors in the Description but $m$ colors in the Question. Could be slightly confusing. Nice question.2011-04-21
  • 0
    @Matthew: The difference was intentional to draw attention to the fact that I'm asking for a *square* grid not the rectangular, general case of the game. Thanks for your comment.2011-04-21
  • 0
    Do neighbouring nodes include diagonally adjacent nodes? Also, the example you drew happens to be staircase-shaped -- do I understand correctly that that's not a requirement and the cluster can extend into the grid in an arbitrarily complex shape?2011-04-21
  • 0
    See also http://stackoverflow.com/q/1430962: "How to optimally solve the flood fill puzzle?"2011-04-21
  • 0
    @joriki: no, neighbors are only horizontal and vertical. Yes the cluster can be of any shape.2011-04-21
  • 0
    @Hans: Thanks! That's a better name to search for.2011-04-21

1 Answers 1