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:
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?