1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Note that a related puzzle has been shown to be NP-Hard, so I'd expect similar for this one too. If your instances are small, that likely is not a problem, but you should temper your expectations of finding a polynomial time algorithm for the optimal solution. \$\endgroup\$
    – DMGregory
    Jun 23, 2020 at 20:29
  • \$\begingroup\$ Evolutionary/genetic algorithm might be good enough. For rare cases when player does better than your AI, reward player for being genius. \$\endgroup\$ Jun 26, 2020 at 7:02

1 Answer 1

4
\$\begingroup\$

My advice would be to generate the puzzles by running your solving algorithm in reverse: Add connected shapes that displace the squares they occupy and the squares above them up.

The number of shapes you add may not be the minimal amount of moves to solve the puzzle but it will give you a good estimate of a good solve. Anything below that number will probably be a great solve, especially if you use some heuristic to minimize shapes of the same color in overlapping or neighboring columns during generation.

\$\endgroup\$
1
  • \$\begingroup\$ That's good advice, thank you :) I'll try to come up with a good algorithm to generate puzzles in this manner. It also sounds easy to add the varying degrees of difficulty to it with the heuristic that you mention. \$\endgroup\$
    – Robert
    Jun 23, 2020 at 22:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .