Suggest an algorithm and data structure for solving the game Globs (http://www.deadwhale.com/play.php?game=131). It's pretty fun in a geeky kind of way.
State the time-space complexity (big-O) of your approach in terms of N, the size of the grid (N>=14). Good-enough efficient algorithms with low complexity are preferred.
(MatrixFrog correctly points out this game is also known as FloodIt, and Smashery gave a solution 3 months ago in the link he cites below. All you dudes suggesting pruning/greedy with only 1 lookahead, that gives suboptimal solutions.)
The game generates a random square grid of nxn nodes, where each node is colored one of six colors (Grn=1, Ylw=2, Red=3, Blu=4, Pur=5, Orn=6). Level 1 has a 9x9 grid, then n increases each level, up to 14. Each level you can take up to 25 turns or else you lose. On each turn you choose which color to change the top left node to e.g. Grn->Red, such that any connected adjacent (horiz/vert) nodes of the new color get assimilated into shape, and 1 pt per node assimilated is ADDED to your score. The scoring objective is to complete each grid in as few turns as possible, e.g. if you do it in 16 turns, then your 9 unused moves => 2*9 MULTIPLIER times your total accumulated score.
Obviously, there are a ton of ways to decompose this, and the default choice of recursive backtracking with a 14x14 grid is a viable contender; What other types of data structures does this lend itself to? A *? Don't get hung up on optimality, I'm wondering if there is a "good enough" algorithm.
(I thought it might be a fun project to code up a robot and get silly-high scores. Although I scored 3.5E+12 all by my flesh were self.)