Solving Rush Hour, the Puzzle (2018)

Since the author seems interested in the maximum number of moves required to solve the puzzle, a similar puzzle called Subway Shuffle far outdoes Rush Hour. For example, puzzle 100 involves 9 pieces on a 10-spot grid, but requires (as far as is known, maybe the solution isn't optimal?) 589 steps to solve. https://www.cs.brandeis.edu/~storer/JimPuzzles/ZPAGES/zzzSub...

▲

pavel_lishin 2 days ago | parent [-]

Does anyone know if a version of this is available for Android? I've had no luck searching.

It also seems like something that would be great as part of Simon Tatham's puzzle collection: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ / https://play.google.com/store/apps/details?id=name.boyle.chr...

▲

gcanyon a day ago | parent [-]

I had the app installed way back when, and it was fun. I reached my limit around 60-90 step solutions. The numbers are a little deceiving: in many cases there are sequences of moves 3, 4, or 5 (or more?) long where only one move is possible, and therefore in a sense they qualify as only one decision as a unit, even if they are multiple moves. I think this same aspect is sometimes true of Rush Hour, but less so.

As far as I know it was iOS-only. I think the author created the puzzle as a phd paper, and once I found the paper itself online. It was interesting reading.

It should be possible today to vibe code the mechanics as a web app, right?

	▲	pavel_lishin a day ago \| parent [-]
		> It should be possible today to vibe code the mechanics as a web app, right? Probably, but I ain't got the interest to.

▲

tromp 2 days ago | parent | prev | next [-]

It turns out that Rush Hour becomes much harder if we shrink the cars from size 2x1 to size 1x1, while maintaining their direction to be either horizontal or vertical [1]. While the hardest 6x6 Rush Hour puzzle takes 51 moves, the hardest Unit Rush Hour puzzle takes a whopping 732 moves [2].

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

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

▲

ohc 2 days ago | parent | prev | next [-]

Great article, very impressive to solve the entire game, rather than just individual puzzles.

PS: Good chance that if you're reading these comments that you will appreciate this video by 2swap, visualising solutions to Rush Hour in 3D: https://youtu.be/YGLNyHd2w10?si=fGFqzEbmV3utbA0O

▲

sameermanek a day ago | parent | prev | next [-]

A little shameless plug:

Ive just released a game built around this project on play store - https://play.google.com/store/apps/details?id=com.noobgiraff...

Has 4x4, 5x5 and 6x6 puzzles. Generating 7x7 puzzles is long process and i think i may have to do it on cloud, but am planning to release them soon.

▲

mzl 2 days ago | parent | prev | next [-]

Fun article.

The Rush Hour puzzle is quite fun when viewed as a planning problem. In standard PDDL the model becomes very messy. I like the extensions proposed in https://arxiv.org/abs/2412.06312v1 that makes the model intuitive.

▲

jasonjmcghee 2 days ago | parent | prev | next [-]

I played this a lot as a kid. There are so many "levels" - it's fantastic and addictive - but like in a good way where you're using your brain.

▲

Simon-curtis 2 days ago | parent | prev [-]

Thanks for the article, perfect timing. Was stuck on a secret Santa gift for the brother in law. Rush hour is perfect!