Minimal: a state where each piece is important.The puzzle cannot be made any harder by moving the pieces around. Unsolved: a state that is further from a goal state than any other reachable state.Note that there's no need to model the primary piece actually exiting the board. Goal State: any state where the primary piece is on the target square (all the way to the right).Move: moving a piece by N steps at once.Primary Piece: the "red car" in the puzzle, the piece that must reach the exit on the right side of the board.In Rush Hour there are 2-pieces (cars) and 3-pieces (trucks). Each piece has a position, a size, and an orientation (horizontal or vertical). My code is open source with a permissive license and the resulting database is available for download. It was quite challenging (and exciting!) and that's what I want to talk about in this article. Ultimately I ended up with a complete database of every "interesting" starting position. Unsatisfied with the results, I then decided to try generating all possible puzzles. The generator used simulated annealing to try to maximize the number of moves required to solve the puzzle. We've been having fun with it, but naturally I was most interested in writing some code to solve the puzzles.Īfter writing a solver, I wrote a puzzle generator that would create more starting positions for us to try (the game comes with 40 levels printed on playing cards). Recently, I stumbled on the physical incarnation of it and instantly bought it on Amazon for my kids to play. I played a clone of this game on my first iPhone several years ago. It was first sold in the United States in 1996. Rush Hour is a 6圆 sliding block puzzle invented by Nob Yoshigahara in the 1970s.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |