I am writing a Python program that solves a 2x2x2 rubiks cube using A* and beam search. However, if I scramble the puzzle more than ten times the program keeps running forever, and I think it is because the heuristic I am using is incorrect. My heuristic function just counts the average number of unique colors on each face of the rubik's cube and returns it, but I am not sure how to test if it is admissible. Can someone give me tips on how to check whether the heuristic is admissible or not? Thank you.

  • $\begingroup$ Are you caching configurations so that you don't visit them twice? The search space is very small, and even brute force should be pretty fast. Your heuristic will probably work fine as long as you stop retreading the same ground. $\endgroup$ – rschwieb Oct 20 '17 at 3:01
  • $\begingroup$ I use a hashtable to keep track of nodes that are already visited, so yes, nodes should not be visited twice. $\endgroup$ – noob Oct 20 '17 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.