Solving AlienTiles with an A* heuristic

Question

Hello I am trying to solve the AlienTiles problem described at alientiles.com using the A* algorithm but I cannot find any good heuristic function so far.

In AlienTiles you have a board with $N \times N$ tiles, all coloured red. By clicking on a tile, all tiles in the same row and column advance to the next color, with the colour order being red $\rightarrow$ green $\rightarrow$ blue $\rightarrow$ purple, resetting to red after purple. A goal state is a state where every tile has the same colour, as long as its not red.

Is there any good point to start? I am completely frustrated about how I am supposed to handle the problem. An easy function that I came up with was the distance of the colour of the current tile with the target tile, but it is very slow.