Flood It!

Here is my version of the popular "Flood It!" game for Android. I played the game a lot on my phone and always wondered if there was an algorithm that could find the best solution for any "Flood It!" game, then I found this article that demonstrates the problem is NP-hard for boards of height 3 or more. That did not stop me and I tried to build the best algorithm I could. I decided to program it in JavaScript because I wanted to learn a new language and wanted it to be available to anyone. I implemented the game and the following algorithms:

• Greedy Approach. Pick the colour that results in the largest gain (number of acquired tiles). The number of moves for this approach is calculated for every new table. The colour with the black wide border is the one that gives the largest gain at any stage.
• Force (Brute force approach). Typical brute force algorithm, tries all the combinations and returns the solution with the minimum moves. It can take very long for tables of more than 3 colours.
• SD  (Shortest Distance). To undestand this algorithm and SD2 we have to define the shortest distance to a tile, this value is the minimum number of moves needed to flood a concrete tile. In this approach at each stage we calculate the matrix of shortest distances after choosing every next colour. The color which gives the table which sum is minimum is the color we pick.
• SD2 (Shortest Distance 2). In this approach at each stage we calculate the matrix of shortest distances before and after choosing every next colour. Then we compare only the maximun values. The color which reduces the most the maximum values in the shortest distance matrix is the chosen one. This is my best try but is difficult to compare to the optimal solution as the force approach takes too much time.

The solutions are displayed on the left pane using numbers, 1 for red, 2 for yellow ... moreover you can play pressing the numbers on the keyboard.