Graph search or shortest path algorithm for graph with multiple “goals”?

I did a project in a class using A* search to solve an 8-puzzle. But what about a puzzle with multiple ‘solved’ states? For example, and 8 puzzle with some repeated tiles. I’m not sure whether something like A* search could still work or not. I have trouble fathoming how a heuristic might be designed. Are their other shortest path algorithms or search algorithms that are better suited for this kind of problem?