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?