Rush Hour
if you're not familiar with it, the game consists of a collection of cars of varying sizes, set either horizontally or vertically, on a NxM grid that has a single exit.
Each car can move forward/backward in the directions it's set in, as long as another car is not blocking it. You can never change the direction of a car.
There is one special car, usually it's the red one. It's set in the same row that the exit is in, and the objective of the game is to find a series of moves (a move - moving a car N steps back or forward) that will allow the red car to drive out of the maze.

I've been trying to think how to solve this problem computationally, and I can really not think of any good solution.
I came up with a few:

1. Backtracking. This is pretty simple - Recursion and some more recursion until you find the answer. However, each car can be moved a few different ways, and in each game state a few cars can be moved, and the resulting game tree will be HUGE.
2. Some sort of constraint algorithm that will take into account what needs to be moved, and work recursively somehow. This is a very rough idea, but it is an idea.
3. Graphs? Model the game states as a graph and apply some sort of variation on a coloring algorithm, to resolve dependencies? Again, this is a very rough idea.
4. A friend suggested genetic algorithms. This is sort of possible but not easily. I can't think of a good way to make an evaluation function, and without that we've got nothing.

So the question is - How to create a program that takes a grid and the vehicle layout, and outputs a series of steps needed to get the red car out?

Sub-issues:

1. Finding some solution.
2. Finding an optimal solution (minimal number of moves)
3. Evaluating how good a current state is

Example: How can you move the cars in this setting, so that the red car can "exit" the maze through the exit on the right?