The hardest Rush Hour position
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!
Filed under: math | 8 Comments
Tags: configuration spaces, games, graph theory, matthew kahle, puzzles, rush hour, topology
Blogroll
-
Recent Comments
JSE on The Scarlet Plague Richard Séguin on The Scarlet Plague voloch on The Scarlet Plague GrantOster on The Scarlet Plague Why not? « Quo… on Orioles pre-mortem 2012
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.