To examine all possible puzzles, we need an efficient way to enumerate all possible piece placements based on our rules. Solving a 51-move Puzzle Enumerating States * times are from an iMac with a 3.4 GHz Intel Core i5 (4 cores) Bitboards Note that while there are tens of billions of possible states, there are only about half a million puzzles that meet our criteria of interesting-ness. I think solving the 7x7 case may be doable but would require extensive computing resources that I can't afford! (It would probably require decades of CPU time.) Even adding walls increases complexity significantly, so I have only solved the case of 0, 1, or 2 walls. So, writing efficient code and using clever algorithms will be important but will only get us so far. Rush Hour is a perfect example of combinatorial explosion. The database should be complete - any cluster that satisfies the above rules should be included.(This rule drastically reduces the size of the database but adds some processing time.) Removing any piece will alter the solution. Database entries should be "minimal" - each piece in the puzzle is important.Database entries should be fully "unsolved" - they cannot be made any harder by moving pieces around.There should only be one database entry per cluster - no two entries in the database should be reachable from one another.However, walls may be present to the left of the primary piece. That would allow other cars to exit the board too. No horizontal piece may appear on the primary row except for the primary piece itself.These just form walls of pieces that can never move. No row may be completely filled with horizontal pieces and no column may be completely filled with vertical pieces.So, what do I mean by "interesting"? I established a set of rules to filter out a lot of nonsense puzzles. The second paper mentioned that it took on the order of 100 hours for their code to run. But no where did I find any sort of complete database, just a handful of the hardest configurations and a few charts. The second was more interesting and gave me some ideas. Also it was optimizing number of "steps" (versus "moves" - steps being unit moves) which seemed an unnatural way of thinking about it to me. It seemed they were more interested in taking an unusual approach rather than just solving the problem. The first one was rather academic and not particularly helpful.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |