My strategy with the harder levels was to divide it into 2 parts:

1) Ignore the colors and just figure out how to get the pieces on the goal squares (working backwards helps a lot).

2) Find a cyclical part of the puzzle that lets you swap the order of tiles.

Then you just look for any color-agnostic states in Part 2 that overlap with Part 1.