2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Apr 10, 2019 at 21:35
  • $\begingroup$ 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? $\endgroup$
    – Conor Henry
    Apr 10, 2019 at 21:37
  • $\begingroup$ 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! $\endgroup$
    – D.W. ♦
    Apr 10, 2019 at 21:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.