3 ms·
I wonder how good A-star would be at solving something like this? The hard part would be figuring out a good heuristic, but I bet with some experimentation you
by OskarS 9y ago
I wonder how good A-star would be at solving something like this? The hard part would be figuring out a good heuristic, but I bet with some experimentation you could come up with something (number of correct facelets, or cubelets, or number of moves to correctly place all cubelets if they moved independently...).
Probably hard to make the heuristic admissable though, so the solution wont be optimal.
- reikonomusha 9y agoFor the pocket cube, you can just enumerate all positions. It's a very small space.
- lostcolony 9y agoFor larger Rubik's cubes, a naive A* won't cut it, as it still has exponential growth. Iterative deepening A* built atop a pattern database has worked well though. This paper from 1997 also discusses heuristics - https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf https://www.cs.princeton.edu/courses/archive/fall06/cos402/p... And since I'm pulling from Udacity's AI course anyway, might as well provide this; the 3x3 has been fully solved. Depending on the metric - http://www.cube20.org/ http://www.cube20.org/ or http://www.cube20.org/qtm http://www.cube20.org/qtm
- OskarS 9y agoThe point with having a good heuristic is to avoid having to walk the vast majority of the search space, so I wouldn't have thought the exponential growth was that big of a problem. But I guess it's harder than I thought.