13
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ The highest number of moves for the cards in the game, or the highest possible number of moves? $\endgroup$ – Aza May 27 '14 at 23:13
  • $\begingroup$ The highest possible number of moves. $\endgroup$ – Joe Z. May 27 '14 at 23:59
  • 1
    $\begingroup$ @JoeZ. might I suggest you edit your clarification in to the question (and then flag all these comments as obsolete)? $\endgroup$ – msh210 May 28 '14 at 4:23
  • $\begingroup$ On what board size? You can easily require th(m*n) moves solution on an m*n board by having a giant snake of 1x1 cars and only one free space. $\endgroup$ – John Dvorak May 28 '14 at 14:03
  • $\begingroup$ Standard 6x6 board, maximum of twelve 2x1 cars and four 3x1 cars, only the red car is horizontal on the third row. $\endgroup$ – Joe Z. May 28 '14 at 14:03
11
$\begingroup$

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/ .

$\endgroup$
  • $\begingroup$ Although I'm very interested in the math, I'll mention for those strictly looking for puzzles that most of them in that paper (though not all) are right near the bottom, in Annex E. $\endgroup$ – Wildcard Apr 29 '17 at 7:29
  • $\begingroup$ And ulb.ac.be/di/algo/secollet/papers/crs06.pdf is quite related, though it doesn't appear to go into it in as much detail as the thesis you linked. $\endgroup$ – Wildcard Apr 29 '17 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.