Timeline for Will a greedy algorithm solve Tatham's Flood?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 14, 2017 at 14:29 | vote | accept | Rand al'Thor | ||
| Dec 17, 2016 at 17:42 | comment | added | Ian MacDonald | I first encountered this game back in 2010 on BlackBerry. It was titled Pixelated. The rules of the game required a solve within 21 moves. I'm not sure if it was guaranteed to be possible, though. There were certainly many grids that I personally failed. Would be interesting to compare that number with an optimal solution found here. | |
| Dec 16, 2016 at 22:50 | comment | added | Rand al'Thor | @Ian I don't count "making the whole grid monochromatic" as solving it - that's always possible. To really solve it, you need to fill the grid optimally. | |
| Dec 14, 2016 at 18:17 | comment | added | Ian MacDonald | The answer to the title question is obviously "yes". ;) | |
| Dec 14, 2016 at 17:41 | answer | added | Max Hoffman | timeline score: 3 | |
| Dec 13, 2016 at 9:39 | answer | added | dtldarek | timeline score: 39 | |
| Dec 13, 2016 at 9:04 | comment | added | Taemyr | @MikeEarnest you should make that an answer. | |
| Dec 13, 2016 at 8:14 | answer | added | EmFi | timeline score: 5 | |
| Dec 13, 2016 at 7:32 | answer | added | Shirkam | timeline score: 2 | |
| Dec 13, 2016 at 7:29 | answer | added | Glen O | timeline score: 5 | |
| Dec 13, 2016 at 1:13 | comment | added | Rand al'Thor | @MikeEarnest Thanks, very interesting! | |
| Dec 13, 2016 at 0:13 | comment | added | Mike Earnest | Solving this game is NP-Hard, so there probably aren't any clever algorithms which find the optimal solution quickly. arxiv.org/abs/1001.4420 | |
| Dec 13, 2016 at 0:07 | comment | added | econoMichael | After playing the game for a few minutes I can think of an instance where it wouldn't be optimal: when the most popular-colored block(s) is/are completely encapsulated by the "flood" block. So this colored block would have the most contact with the flood block, but not necessarily expand the flood block's reach if changed to that color. I think more optimal algorithm would be to select the color that reaches the most blocks, so looking two steps ahead rather than one. But your algorithm works because the highest block count will generally connect to the most blocks. | |
| Dec 13, 2016 at 0:07 | answer | added | TheGreatEscaper | timeline score: 42 | |
| Dec 12, 2016 at 23:58 | history | edited | Rand al'Thor | CC BY-SA 3.0 |
added 244 characters in body
|
| Dec 12, 2016 at 23:51 | history | asked | Rand al'Thor | CC BY-SA 3.0 |