How to solve the game of Flood-It

Perhaps, if I find the answers in someone else's code, I won't have to play the darned game anymore.

It turns out that the game is NP-hard; the The Complexity of Flood-Filling Games (from Raphael CliffordMarkus JalseniusAshley MontanaroBenjamin Sach).

I don't feel so bad about it any more.

Some more hard games: Mastermind, Minesweeper.

Advertisements

3 thoughts on “How to solve the game of Flood-It

  1. Jan Wolter

    NP-hard means that it is part of a class of problems for which nobody has ever found an algorithm whose run time doesn’t increase exponentially as the size of the grid increases. However the size of the grid doesn’t increase. All the puzzles at the site I found have a grid of 14×14. This result doesn’t tell us anything about the difficulty of solving 14×14 puzzles.

    Reply
  2. Jan Wolter

    I’ve just noticed that my bathroom floor is a giant four color Flood-It puzzle. I’ll never be able to use the John again without driving myself mad trying to solve it.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s