• tromp 252 days ago

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

• losvedir 252 days ago

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?

• jsnell 252 days ago

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.

• panic 252 days ago

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

• joefkelley 252 days ago

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.

• djflutt3rshy 252 days ago

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

• fogleman 252 days ago

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.

• fogleman 252 days ago

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.

• bumholio 252 days ago

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.

• fogleman 252 days ago

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

• ythn 252 days ago

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

• testaccount7 252 days ago

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

• fogleman 252 days ago

• fogleman 252 days ago

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.

• jsnell 252 days ago

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.

• fogleman 252 days ago

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.

• dang 252 days ago

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

• Someone 252 days ago

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?

• fogleman 252 days ago

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

• flashman 252 days ago

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.

• tromp 252 days ago

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

• prawn 252 days ago

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

• hughes 252 days ago

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 :)

• fogleman 252 days ago

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!

• maaaats 252 days ago

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

• jsd1982 251 days ago

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

• LeonidBugaev 252 days ago

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

• stu_k 252 days ago

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?

• fogleman 252 days ago

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

• ah0y 251 days ago

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.

• tpl 252 days ago

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

• web007 252 days ago

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

• fogleman 252 days ago

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.

• whatever1 252 days ago

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

• eachro 252 days ago

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

• cjslep 252 days ago

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