tromp 2 months 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].

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

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

losvedir 2 months 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 2 months 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 2 months 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 2 months 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.

  • fogleman 2 months 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 2 months 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 2 months ago

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

  • ythn 2 months ago

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

  • testaccount7 2 months ago

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

    • fogleman 2 months ago

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

fogleman 2 months 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 2 months 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 2 months 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 2 months ago

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

Someone 2 months 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 2 months 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 2 months 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.

prawn 2 months ago

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

  • fogleman 2 months ago

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

hughes 2 months 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 2 months 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 2 months 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.

stu_k 2 months 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 2 months ago

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

ah0y 2 months 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 2 months ago

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

web007 2 months ago

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

  • fogleman 2 months 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 2 months ago

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

eachro 2 months 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 2 months ago

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