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?
If you have multiple goal nodes and a consistent (or admissible) heuristic to each of them, taking the minimum of them will be still be a consistent (or admissible) heuristic.
Aside from that, there is nothing in A* that prevents you from having multiple goal nodes.  The algorithm works fine unchanged.

[Edit] Another heuristic for your problem specifically: for each tile, compute the distance to the nearest valid goal-space, then take the sum over all tiles as the heuristic.
With $n$ spaces, $n-1$ tiles, and $g$ goals, this can be done in $O(n)$ time during the pathfinding by pre-computing the distance to the nearest goal, for each tile, using eg. BFS. This will require $O(n^2)$ space and $O(gn^2)$ time (by searching backwards from each goal).