What is the Rush Hour puzzle with the most steps in its solution?

Question

Rush Hour is a well-known sliding-block puzzle in which you push cars around (each car moves horizontally or vertically) to let a red car escape the grid. The standard board is a 6x6 grid, with four 3x1 cars and twelve 2x1 cars available to place on the grid. Only the red car is ever placed horizontally on the third row, which is the escape row.

You cannot get the red car to escape with brute force; solving the gridlock sometimes requires some complicated and at other times counterintuitive manoeuvres. Generally, the more steps a solution has, the harder the puzzle is.

Level 40 in the original set sold by Binary Arts has a solution with 50 steps. But there must certainly be harder puzzles than that. What is the Rush Hour puzzle with the most possible steps in its solution?

Answer 1

Frédéric Servais has apparently done a lot of study of this problem, particularly his Masters' thesis, Finding hard initial configurations of Rush Hour with Binary Decision Diagrams. For the 6x6 case without 'trucks' (3x1 pieces), he finds a maximum of 65 steps (plus the final move of the red car out); for the "full" 6x6 case, the maximum he finds is 92 steps, but it's not as clear to me from the skimming I've done that he has a proof of maximality for that position. You can see diagrams of his top positions (note that move counts are off by 1 for these, since the results on this page count the final move of the escaping car as well) at http://cs.ulb.ac.be/~fservais/rushhour/ .