4
$\begingroup$

I am looking for a good heuristic function for solving a 2D $n\times n$ Rubik's cube using A* search. There is a game already in the play store.

The rules of the game:

enter image description here

Swiping LEFT means the leftmost cube of that row will come to the rightmost position in that row. All other cubes will be moved one position to the left. So it's like a circular shift. The same type of rules apply for UP, DOWN and RIGHT swipe.

The above pictures are for a $3 \times 3$ Rubik's cube, but I'm interested in algorithms that work for the general $n \times n$ case, so the state space might be fairly large.

2 possible heuristic functions that come to my mind:

  • (Total number of mismatches with the goal state) / (number of rows or columns or colors)
  • Average Manhattan distance of each cube with the goal state

Which will work better? And why? Is there any better heuristic function for this problem?

$\endgroup$
  • $\begingroup$ You're going to have to explain the rules of the game. But as a suggestion: Find a safe heuristic first, and prove that it is safe. Remember that if you have more than one safe heuristic, you can always use them both; just take the maximum. $\endgroup$ – Pseudonym Oct 4 '17 at 5:18
  • $\begingroup$ Do you try to find the shortest solution? Then under "heuristic" do you mean a solution that is not much worse than optimal? $\endgroup$ – rus9384 Oct 4 '17 at 9:33
  • $\begingroup$ Does the rules require the color stripes to be at some particular order or it doesn't really matter? Meaning the order red, green, blue is the solution but red, blue, green also counts? $\endgroup$ – Evil Oct 4 '17 at 19:15
  • $\begingroup$ @Evil The heuristic will be same for both, I guess $\endgroup$ – Preetom Saha Arko Oct 5 '17 at 18:04
  • $\begingroup$ The original 3D problem works well with a mixture of two Manhattan metrics, but there is one goal (technically more, since centers might be rotated), but in 2D case where stripes might be horizontal or vertical with any order it would be wasteful to pick one. Something along Multiple-Goal Heuristic Search comes in mind (maybe it is overkill, haven't tested it) or two searches with some preprocessing to pick nearest goal state. "Total number of mismatches with the goal state" <- there are more goals in that case. If you do care about efficiency it should be included $\endgroup$ – Evil Oct 5 '17 at 18:51

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.