It takes 93 moves to solve, per this paper by Collette, Raskin, and Servais. I tried it and got nowhere.
You can think of the space of all possible configurations of vehicles as, well, a configuration space, not unlike the configuration spaces of disks in a box. But here there is a bit less topology; the space is just a graph, with two configurations made adjacent if one can be reached from the other by making a single move. The connected component of configuration space containing the “hardest case” shown here has 24,132 vertices.
I wonder what this graph looks like? What does the path of the cars look like as you traverse the 93-step path; do most of the cars traverse most of their range? How many of the possible configurations of the 13 vehicles (constrained to stay in the given rows and columns, and in the same linear order when two share a row or column) are actually contained in this component? Maybe Matt Kahle knows. By the way, another Matt Kahle-like fact is that among the list of the hardest configurations are some which are not so dense at all, like this one with only 9 cars. It looks like it should be easy, but apparently it takes 83 moves to solve!
Quomodocumque 
It is still an open question whether Rush Hour with *1×1 cars only* (each constrained to move only NS or only EW) on an NxN board has exponentially long puzzles. For N=6, and subject to the additional constraint that all squares but one are occupied, the longest solution is 732 moves(!!) according to pages 12ff. of
John Tromp, Rudi Cilibrasi: Limits of Rush Hour Logic Complexity
(http://arxiv.org/abs/cs/0502068). Here’s the longest 5×5 puzzle, which takes only 199 moves:
| | | | –
– | | – –
| – – | *
| | – – |
| – – – |
(where |-* denote NS car, EW car, and empty space respectively). The horizontal-moving gar in the NE corner needs to escape Westwards.
Having only played rush hour for 15 minutes or so with a niece, is it the case that the “number of moves” required is a good measure of the difficulty of the puzzle? It’s certainly possible to construct “easy” mate in 10 chess problems, but there are some fiendishly difficult mate in 2 puzzles (and even a few tricky mate in 1 puzzles!)
Good question, though this is more like a helpmate than a direct (forced) mate problem (to be sure there’s no difference if it’s mate in 1!). But that’s because the difficulty of chess problems is limited by the constraints of an art form created by and for humans, and this constraint is independent of the length of the problem — so exponentially difficult mates in 10 could never be composed or solved even if they exist. There’s no such constraint here, so length of solution could be a reasonable proxy for difficulty. (NB computer searches have also found mates in hundreds of moves that are way beyond human comprehension even though there are only 4 or 5 pieces on the board besides the kings.)
Is there anywhere where one can attempt to solve this position online? (If not then I’ll have to go upstairs and get out a physical puzzle, but in this day and age that kind of energy expenditure should not be necessary.)
Here are a few options, in case you haven’t already found one: http://britton.disted.camosun.bc.ca/rushhour/links.html
It’s true that you can think of the configuration space of as a graph. But there is a natural higher dimensional-polyhedral complex lurking in the background. I won’t define it in this comment but see Ken Deeley’s article on “Configuration spaces of thick particles on a metric graph”:
http://www.msp.warwick.ac.uk/agt/2011/11-04/p061.xhtml
Aha — in that case, what I wonder is whether the complex containing the hard initial position “resembles” the configuration spaces of disks in a box which are just at the threshold of connectivity
Just stumbled on this, and I just solved it. It was harder than any Rush Hour puzzle I can ever remember doing, but not really excessively difficult. Probably easier and less tedious than a typical AIME problem.
By the way, I think that the minimum number of moves is a reasonable proxy for difficulty, but probably not a very good one for the hardest puzzles.
My brother did this in 51 moves…
My program did this “93” moves configuration with only 49 moves.
Both you guys above should notify the authors of the linked paper!
It really depends how you measure a move. It can indeed by solved in 49 moves, however that’s when a move is defined as moving a single vehicle where distance does not matter. The linked paper defines a move as moving a single vehicle one step, hence they get the 93 steps.
Sorry guys, my fault. Of course, moves of my cars wasn’t restricted on a single step. And so I made it on 49 steps. Maybe if restrict my algorithm on single step it would be worse than 93 steps :) I got this problem as a task in school, it was quite funny :)
[…] first test case is this, with 2 simple cases […]
Actually not that hard, beat it in 5 minutes
a couple of 12th graders just did it in like 3 minutes :)
I suspect that any metric which fails to take into account the number of possible *other* options (besides forward or back) will not give a “hardest” puzzle. From actually working through the standard puzzles, there are many puzzles where despite the apparent complexity of many pieces, solution is easy because there are only two or three possible moves at each step—and one of them is always the reverse of the move you just made.
Some sort of ratio between number of moves required (counting any number of spaces moved by a single vehicle as just one move) and number of total possible configurations of the puzzle, would have to be made.
Regarding the relationship between difficulty for humans and number of steps: “Tower of Hanoi” with n blocks takes O(2^n) steps but is easy. I could imagine Rush Hour having a subfamily of positions with a similar property.