# Heuristic for searching for solutions on an 8-puzzle variant with non-unique tiles

I'm trying to perform an A* search on a particular N-puzzle variant in which some tiles are identical. More specifically, assuming an $$m \times m$$ grid, there are m colors with m tiles of each. The puzzle is considered solved when tiles form vertical lines of matching color. For example, with $$m=3$$

RG       GR     GR      RGB
RGB     BGR     GRB     RG      etc.
RGB     BGR     GRB     RGB


would all be valid solutions.

I am having difficulty coming up with a good heuristic for this, as any one tile could potentially occupy any one of the m*m locations when solved. Could anyone offer any suggestions or advice? Perhaps another type of search algorithm would be better?

• Cross-posted: cs.stackexchange.com/q/106698/755, stackoverflow.com/q/55409613/781723. lease do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. – D.W. Apr 10 '19 at 21:35
• Sorry, I originally posted on SO before realizing this was the better place for the question. Should I delete the post over there? Or what's the proper way to handle this? – Conor Henry Apr 10 '19 at 21:37
• Yeah, if you post on the wrong site, just delete the copy on the wrong site before posting on the new site, then you're all sorted. And welcome to CS.SE, by the way. I hope someone here can help with your question! – D.W. Apr 10 '19 at 21:41