A Rubik's cube can obviously be generalized to an ordered set and a set of permutation operations on that ordered set. The goal is to restore a permuted ordered set to its original order.
(This does not cover puzzles in which certain moves become not possible in certain states, e.g., bandaging.)
How difficult is solving these problems in general? I would not be surprised if it is something like PSPACE-hard. There are several questions: Is a given puzzle configuration solvable? What is a solution? That is, give an algorithm which will find a solution from any initial scramble. What is the shortest solution, or some relatively short solution? Analyzing the Rubik's Cube with group theory offers heuristics leading to short solutions (Kociemba): how does one do this for general permutation puzzles?
No comments :
Post a Comment