Lemma Soft Forums

The Rubik’s Cube is a well-known combination puzzle that has been a popular case study in artificial intelligence due to its simplicity to present but difficulty to solve. If one considers the most popular version, a 3×3×3 cube, the goal is explicit and yet there exist over 4.3×10^19 permutations available from a given configuration (Korf, 1997). This problem size readily implies that any automated system for solving the cube optimally must have a great deal of thought devoted to optimisation itself, in order to obtain a solution within a feasible amount of both time and space.

If the number of moves in a solution were not important, then one could relatively easily implement the strategies for solving used by humans; with a predetermined strategy of sub-problems, only a small number of algorithms for specific tasks need to be memorised. However, this is trivial for an AI and thus finding an optimal solution (i.e. minimising the number of moves) is a more interesting and challenging problem. To approach this problem, the cube must first be translated into a problem space model, with which applicable algorithms and approaches can be explored and, in particular, compared and contrasted. These different approaches can be investigated both theoretically and experimentally, with the style of the model developed influencing the choice of language and environment used. It is intended that the most time- and space-effective algorithm be deduced or, more likely, which combinations and augmentations of these different algorithms give rise to the most efficient solutions.

The Rubik’s Cube is modelled as a single-agent pathfinding problem: by enumerating all valid permutations of the cube as the set of possible states, with a number of legal operations which can be used to transition between states, the problem can be expressed as a tree with the root node being the initial (scrambled) state and the goal state explicitly known and indeed constant between problem instances. There exist many different search algorithms on this style of problem which can be investigated, as effectively compiled and reviewed by Korf (2010). A prediction based on this review is that the iterative deepening A* algorithm (IDA*), as first outlined by Korf in 1985 and later analysed by Korf et al. (2001), may prove to be the most effective approach overall. The concept of heuristics will also be extended by investigating the use of pattern databases (Culberson and Schaeffer, 1998). This particular combination, also explored by Korf (1997), gives rise to a proportionality between the space available for a lookup table and execution time, which will also be explored.