Flood-it has been proven to be NP-hard. So, there really isn't any reduction that will make the problem easy.
Stackoverflow question without much good content, other than a suggestion to use A* (duh.)
This puzzle was the basis for an About.com programming challenge. The winning solution's strategy was not immediately clear to me.
Unflood It on google code, a python implementation that does a purely heuristic search.
Haskell implementation, pruned depth-first search.
Nice blog entry on a python implementation which is also doing heuristic search.