Show HN: Solving Rush Hour, the 6x6 Sliding Block Puzzle | Hacker News Reader

Show HN: Solving Rush Hour, the 6x6 Sliding Block Puzzle

michaelfogleman.com

223 pointsfogleman46 comments

Many years ago I investigated [1] the problem of Rush Hour with minimal size cars. I called it Unit Rush Hour, as the cars are just 1x1, but restricted to either horizontal or vertical movement. Interestingly, the puzzles can also be viewed as a kind of maze with restricted movement. My web page has the hardest 4x4 and 5x5 instances in playable form. I found the hardest 6x6 puzzle to require a whopping 732 steps [2].

[1] http://tromp.github.io/orimaze.html

[2] http://tromp.github.io/rh.ps

The link to the "famous 15 puzzle" is dead fyi http://bd.thrijswijk.nl/15puzzle/15puzzen.htm

Thanks for pointing that out. Should be fixed now.

Nice! I like how the piece directions are indicated in the GIF.

Very cool!

I'm interested in the "hardest" 6x6 puzzle. You show the one that takes the most moves to complete, but I don't think that's necessarily very difficult, if they're all pretty straightforward. Rather, I think the hardest puzzle is one where you have a lot of options to choose from. IOW, a very broad tree, rather than a very deep one. Are you able to quantify the hardest puzzle along those lines somehow?

One simple idea I had was NumMoves * log(ClusterSize) as a difficulty metric. But I'm not sure. I had my wife play several different puzzles to try to gauge difficulty based on that but it didn't seem so clear cut.

What we the people are demanding are insanely hard puzzles. Not an enumeration of hard games on the 6x6 board, but a heuristic generator for the 7x7 or the 8x8 or even the 10x10 if need may be, of games that seem utterly intractable for the first few hours.

Haha. Well, if you have ideas I'm all ears!

Not just a broad tree, but a labyrinthine broad tree where you are basically traversing a maze of choke points

ThinkFun, the US publishers of Rush Hour, wrote a blog post about this when they made the mobile app with a bunch of autogenerated levels maybe around 2010. Unfortunately that article is basically impossible to find now, since they redid their website and deleted the old posts. (I say "impossible", since I spent a couple of hours looking for it again while reading papers on procedural puzzle generation last year. Maybe somebody here has better luck).

The basic metric their level generator used for quantifying interesting difficulty was the earliest point of non-trivial divergence in solutions. I.e. if there's a puzzle with a 50 and 51 move solution, having those solutions diverge on move 3 is interesting. Having them diverge on move 45 isn't.

I wonder if this is the article you're thinking of:

https://web.archive.org/web/20100221131225/http://www.thinkf...

(The text of the article is only visible at the very bottom of the page for some reason)

Awesome find, thanks! Wonder if I can find this Mark Engelberg fellow...

He also made an original game with ThinkFun: Code Master, which does some fun stuff with state machines:

https://www.thinkfun.com/products/code-master/

That's it, thanks! (And to romellem for the link with a working layout and images.)

Through hcs's reply below, I was able to come across a better link to the original blog post:

Thinkfun & Mark Engelberg, "The Inside Story of How We Created 2500 Great Rush Hour Challenges"

https://web.archive.org/web/20130703141244/http://www.thinkf...

One way this could be calculated is to assign transition probabilities to the edges, and calculate the expected number of steps a random walk takes to reach the end. (wikipedia has the math required: https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expecte...)

I'm not sure how best to assign probabilities, or how sensitive it would be to that. Perhaps uniformly, or perhaps biased toward moving closer to the end state.

http://cs.ulb.ac.be/~fservais/rushhour/ has a listing of puzzles that take the most moves, but also mentions how many different configurations are possible.

The guy who made the website literally wrote his master's about it: http://code.ulb.ac.be/dbfiles/Ser2005mastersthesis.pdf

I linked to this in the Prior Art section. This is the one I wasn't very impressed with. For one, his "moves" are unit-steps.

Check out the paper "Difficulty Rating of Sokoban Puzzle": https://pdfs.semanticscholar.org/880f/32f843e8e1fe9c712b0fc4... -- in particular the "problem decomposition" model introduced at the end. Being able to break a solution into subproblems makes it easier, even if there are a lot of steps (see Figures 5 and 6 in the paper).

A bit tangential but Peter Norvig talks about hard puzzles some in norving.com/sudoku.html

I like Peter Norvig. You inspired me to email him about this.

Just finished this write up documenting my latest side project. I've been a bit obsessed with this problem for the past few weeks. Hope you like it! Be sure to check out the puzzle database and let me know if you do anything cool with it.

Just FYI, Show HN isn't meant for blog posts. It's for things that can be interacted with. See: https://news.ycombinator.com/showhn.html

You might want to edit the title.

There's code and data that people can "try out". Some of my past Show HNs have been of a similar format. But if a mod wants to edit the title, go ahead.

It's borderline, but as long as there's working code we tend to allow these.

http://www.ulb.ac.be/di/algo/secollet/papers/crs06.pdf claims a 6x6 board that requires 93 moves.

That could be a matter of counting moves differently (if you move a car two places, is that one or two moves?), but I think that’s unlikely, as it would require about forty such multi-step moves.

So, who’s wrong? You, that paper, or me?

Mentioned this in the Prior Art section and another comment here, but his "moves" are single-square steps.

Running my solve utility on his hardest puzzle yields:

$ go run cmd/solve/main.go BBBCDEFGGCDEF.AADEHHI....JI.KK.JLLMM {true [A-1 C+2 B+1 E+1 F-1 A-1 I-1 K-2 D+2 B+2 G+2 I-2 A+1 H+1 F+4 A-1 H-1 I+2 B-2 E-1 G-3 C-1 D-2 I-1 H+4 F-1 J-1 K+2 L-2 C+3 I+3 A+2 G+2 F-3 H-2 D+1 B+1 J-3 A-2 H-2 C-2 I-2 K-4 C+1 I+1 M-2 D+2 E+3 A+4] 49 93 49 12266 1494475}

93 steps, but just 49 moves.

That puzzle is on line 13 of my database:

49 BBBKLMHCCKLMH.AALMDDJ....IJEE..IFFGG 24132

https://www.michaelfogleman.com/static/rush/rush1000.txt

FWIW I think your approach to counting moves is more logical. We're more interested in understanding how many intermediate states a puzzle has between its initial state and solution. Whether you move a piece by one square or three is not particularly interesting.

Btw, if you like Rush Hour, I highly recommend Antivirus (terrible name for Googling) by Smart Games [1]. The pieces come in 9 distinct shapes along with 2 wall pieces, which give most puzzles a unique character. Computational investigation shows that the hardest possible puzzle requires over 200 moves to solve. Beyond that, the game looks and feels fantastic [2].

[1] http://www.smartgames.eu/en/smartgames/anti-virus-classic

[2] https://www.youtube.com/watch?v=71CWtqH-csM

Interesting, detailed and well-presented. Well done. My son loves this game. I'll show him the hardest ones you generated.

My 5-year old son says "I can't figure it out, it's too hard!"

Mine was 4-5 yo when he first saw it, and got it very quickly. Some people are just wired for this sort of puzzle I think.

He also loves Gravity Maze: https://www.thinkfun.com/products/gravity-maze/

Great work! Was nice seeing this come together on Twitter over the past couple weeks.

Would you mind adding a date to the article? Will make future comparisons to `current "state of the art"` more useful :)

Thanks for calling me out on that. I hate it when online content is missing a date. There is a date on the "More" page that links to this, but it should be on the page itself too!

> Ultimately I ended up with a complete database of every "interesting" starting position.

That's a nice thing to strive for. I love puzzle games, but I have come to realize there's a big difference in how different apps generate their games. For instance, Simon Tatham's Puzzle Collection is mostly very good. But for the "Loopy" game, I have liked the variants from the app "Slitherlink" more. Same game, but the challenges presented makes the difference.

I tackled this myself several years ago but the game was called Un-block Me on Android. Just did a basic BFS implementation in C#. Worked quite well.

https://github.com/JamesDunne/UnBlockMeSolver/blob/master/Un...

I wonder home much efficient solution will be if written in the logic programming language like Prolog.

PS. Find this one, but did not run any analysis yet: https://github.com/nablaa/rushhour-solver-prolog

This is great, I love rush hour.

Is there an web based version of the game where I can try some of these generated puzzles?

I never actually looked for one! I considered implementing my own but haven't gotten around to it yet.

Awesome. Have you consider [3] set (red car in 3 square, AAA) for primary row? The article state you only consider [2] set and I checked the database doesn't have element in [3] set. I ask it out of curiosity because some variant include 3-square red car.

This has been fun to follow on his twitter as well. He is a great person to follow!

I couldn't tell from the description of "minimal" - did you discount horizontal symmetry to reduce your set size by half?

The exit is on the right, so there is no horizontal symmetry. For odd sized boards there is vertical symmetry, which I haven't addressed since I was mainly concerned with 6x6.

Why not use Constraint Programming / Integer Programming? Provide a budget of maximum moves, seek the best possible solution.

What solvers is he using? Is it really just some sort of simulated annealing? I would have expected A* search at a first glance.

Awesome! I loved playing this game growing up. Cool to see it again, here.

Reply on news.ycombinator.com