Posting’s going to be abnormally slow here the next two weeks. I’m currently ramping up into a new project at work while another one is just winding down. While there’s overlap, I’ll probably be pretty busy. There’s also some Good Things in the works about which I’m reticent. I’ll post more about them if they pan out.

I do, however, have a few posts in the works about a variety of things; Quines and the CLR and hacker drama, oh my!

So stay tuned. But while you’re staying tuned, here’s an intersting quandary:

So the game Flood-It (to which I’m fair addicted) has recently been proved NP-Hard. The game is fairly simple. From the abstract of the linked article:

“In this game the player is given an n by n board of tiles where each tile is allocated one of c colours. The goal is to make the colours of all tiles equal via the shortest possible sequence of flooding operations. In the standard version, a flooding operation consists of the player choosing a colour k, which then changes the colour of all the tiles in the monochromatic region connected to the top left tile to k. After this operation has been performed, neighbouring regions which are already of the chosen colour k will then also become connected, thereby extending the monochromatic region of the board.”

So my question: what constraint of the above problem, other than finding the shortest sequence, could one relax or eliminate to move this problem from NP into P? I strongly suspect that, were a player allowed to choose their starting square after having seen the initial board coloring, that all board configurations would be solvable in P. I haven’t proved this yet, though, so I may very well be wrong.

Thoughts?