Solving Rush Hour, the Puzzle (2018)

https://www.michaelfogleman.com/rush/

63•xeonmc•2mo ago

Comments

gcanyon•2mo ago

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•2mo ago

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•2mo ago

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•2mo ago

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

Probably, but I ain't got the interest to.

mzl•2mo ago

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.

tromp•2mo ago

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

Simon-curtis•2mo ago

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

ohc•2mo ago

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

jasonjmcghee•2mo ago

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.

sameermanek•2mo ago

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.

Show HN: Knowledge-Bank

Show HN: The Codeverse Hub Linux

Take a trip to Japan's Dododo Land, the most irritating place on Earth

British drivers over 70 to face eye tests every three years

BookTalk: A Reading Companion That Captures Your Voice

Is AI "good" yet? – tracking HN's sentiment on AI coding

Show HN: Amdb – Tree-sitter based memory for AI agents (Rust)

OpenClaw Partners with VirusTotal for Skill Security

Show HN: Seedance 2.0 Release

Leisure Suit Larry's Al Lowe on model trains, funny deaths and Disney

Towards Self-Driving Codebases

VCF West: Whirlwind Software Restoration – Guy Fedorkow [video]

Show HN: COGext – A minimalist, open-source system monitor for Chrome (<550KB)

FOSDEM 26 – My Hallway Track Takeaways

Show HN: Env-shelf – Open-source desktop app to manage .env files

Show HN: Almostnode – Run Node.js, Next.js, and Express in the Browser

Dell support (and hardware) is so bad, I almost sued them

Project Pterodactyl: Incremental Architecture

Styling: Search-Text and Other Highlight-Y Pseudo-Elements

Crypto firm accidentally sends $40B in Bitcoin to users

Magnetic fields can change carbon diffusion in steel

Fantasy football that celebrates great games

Show HN: Animalese

StrongDM's AI team build serious software without even looking at the code

John Haugeland on the failure of micro-worlds

Show HN: Velocity - Free/Cheaper Linear Clone but with MCP for agents

Corning Invented a New Fiber-Optic Cable for AI and Landed a $6B Meta Deal [video]

Show HN: XAPIs.dev – Twitter API Alternative at 90% Lower Cost

Near-Instantly Aborting the Worst Pain Imaginable with Psychedelics

Show HN: Nginx-defender – realtime abuse blocking for Nginx