GL1zdA wrote:
Oskar45 wrote:
BTW, one of his puzzles [among the most popular of all time] is "Rush Hour". I don't know whether it's available under Android - but if you have an iPad/iPhone, get the full version. It costs less than €2.50 and gets you 2500(!) challenges...
I played several variants of Rush Hour and I somehow didn't like it. While I could solve the puzzles through heuristics, it usually boiled down to finding a move you previously haven't seen. The way I solve it is similar to my approach to Sokoban or
Vexed
- discarding moves which are clearly wrong, imagining the endgame and trying to find the moves in between. On harder levels I add chains of moves which result in certain situation on the board. What's your way of finding a solution to Rush Hour puzzles?
I think you are a bit too optimistic
Rush Hour [and Sokoban] are sliding-block puzzles. More than 45+ years ago, Martin Gardner wrote about such puzzles: "These puzzles are very much in want of a theory. Short of trial and error, no one knows how to determine if a given state is obtainable from another given state, and if it is obtainable, no one knows how to find the minimum chain of moves for achieving the desired state."
Well, even today there is no such theory - and there is a perfectly good reason for this: sliding-block puzzles have been shown to be PSPACE-complete. In particular, 10 years ago it was proved that Rush Hour is PSPACE-complete [that Sokoban is PSPACE-complete was shown in 1998].
HOWEVER, the above concerns only the generalized problems. It might indeed be possible to do better with smaller puzzles. The version I play on my iPad/iPhone [ThinkFun/BinaryArts] has a 6x6 board, the blocks are all 1x2 or 1x3 and each block constraint direction is the same as its lengthwise orientation [either horizontally or vertically]. The crucial block to be moved out of the grid [a red car] is always placed on the third row from top [actually, for the general case, even if the blocks are all just 1x2, Rush Hour is still PSPACE-complete]. The curious thing is that whenever I solve one particular puzzle, I'm always told whether or not I'd done so with *minimal* possible moves. This implies to me these guys indeed have an optimal algorithm at hand - I haven't yet figured it out, though...
So, peruse heuristics...