Color Maze AI with A* Search- Heuristic function

Question

Solving Color Maze Puzzle using A* Search is the goal. This is the example of the game https://www.mathplayground.com/logic_color_maze. Basically you want to minimize the cost of movement, and the goal is to color all the maze going through cells. To implement it with A* Search we need heuristic function. I thought of looking at the number of the left colored cells, but it would be pointless. Shouldn't it be the estimated cost to the goal state(where every cell is colored)? Any ideas to work on that?

Answer 1

To be admissible for A* search, a heuristic function must not overestimate the distance left to go. That is, it's fine if it's an underestimate, but an overestimate is not allowed.

So with that in mind, you need to decide what you're trying to minimize with your search. Is it the number of squares traveled before the whole map is colored? In that case, the number of uncolored squares left would be an admissible heuristic, since you certainly need to move over every remaining uncolored square to complete the puzzle.

On the other hand, if you're measuring the number of straight line moves needed, that will require a fancier heuristic, since many squares can be colored in with a single move. I don't have a great idea for one, but perhaps the minimum (or sum?) of the unique X and unique Y coordinates of uncolored squares could work.

There are lots of possible admissible heuristics, so pick one and see if it's good enough for your use case. It might not be the best heuristic, but that just means the search will be a bit less efficient, not that it won't find the optimal route eventually. In the worst case, you wind up with Dijkstra's algorithm (which is equivalent to A* with a heuristic function that always returns 0). Using a good heuristic just speeds things up, as you won't examine as many partial solutions that are likely to be slower than the optimal one.