I'm creating a puzzle game where the player must remove all colored blocks from a grid. When the player selects a block, all adjacent blocks of the same color are removed. Any blocks that have empty cells below them will then fall into those cells. Here's a simple illustration of the mechanic:
https://i.stack.imgur.com/fE7aV.jpg
The game will procedurally generate puzzles with varying degrees of difficulty. When the player completes a puzzle the game will then score the player based on how quickly and, more importantly, how efficiently they solved the puzzle.
The problem I am having is implementing a method of determining the most efficient way of solving a puzzle (i.e. identifying the fewest number of moves possible). Here's an example of a puzzle that was generated:
https://i.stack.imgur.com/Qhgvc.jpg
As a human, I could identify that the fewest number of moves that could be made to solve this puzzle was 11. Here is a gif of the solve:
https://imgflip.com/gif/463qck
However, when I whipped up an application that just clicked blocks at random in order to solve this puzzle, the lowest number of moves that it was able to solve this in was 14. And this was over billions of iterations which took many minutes. Obviously that is not acceptable. I need to find the correct solution and it should be done within seconds.
I also tried to reverse-engineer the generation process but that doesn't work. For example, it could place a blue block in column 1, a bunch of other blocks, a red block in column 1, a bunch of other blocks, then another blue block in column 1. Column 1 could be resolved in 2 moves (by clicking the red block and then one of the blue blocks), which reverse-engineering the generation would not detect.
So, my question:
What kind of techniques or tricks can I implement that will allow the application to resolve this type of generated puzzle quickly and correctly? I'm sadly out of ideas.
