I am trying to find a good A* heuristic function for the problem "alien tiles", found at www.alientiles.com for a uni project.
In alien tiles you have a board with NxN tiles, all colored red. By clicking on a tile, all tiles in the same row and column advance by a color, the color order being red->green->blue->purple, resetting to red after purple. The goal is to change all tiles to the specified colors. The simplest goal state is all the tiles going from red to green, blue or purple. The board doesn't have to be 7x7 as the site suggests.
I've thought of summing the difference between each tile and the target tile and dividing by 2N-1 for an NxM board or or finding possible patterns of clicks as the minimum number of clicks, but neither has been working well. I can't think of a way to apply relaxation to the problem or divide it into sub-problems either, since a single click affects an entire row and column.
Of course I'm not asking for anyone to find a solution for me, but some tips or some relevant, simpler problems that I can look at (rubik's cube is such an example that I'm looking at).
Thanks in advance.