Naive Solution

The “Naive Solution” is an algorithm which does an exhaustive, breadth-first search for a solution. Depending on the number of moves from the starting point, all possible turns are attempted. For example, if the depth is limited to one, there are eighteen (18) turns:6 slices × 3 orientations = 18

For a depth of two, that number increases to 288 total moves. Note that this is less than 18×18 permutations because we do not count redundant moves. For example, if the second turn undoes the first it is not counted. The table below shows the number of turns required. It follows roughly the exponential sequence:

Table

These numbers were obtained from actual execution of the algorithm. Several attempts to arrive at a mathematical function to generate them have so far failed.

Obviously with such a skyrocketing count it’s not expected that a solver based on this approach will be of much use. However, to its credit, it will find the solution using the least number moves (depth) if you don’t count the billions of wrong attempts, or until the heat-death of the universe – whichever comes first.

One challenge popular during the Rubik’s Cube craze was for someone to apply a very limited number of twists to a pristine cube. It is then handed to an opponent who is to restore it using the same number of twists in reverse. Only a depth of two or three was allowed although some experts have been known to handle four and five. The Naive Solution, let loose on a reasonably fast computer could be used to solve such a limited depth problem.

More importantly was that the Naive Solution would serve as a thorough test of the R.I.C. and provide valuable bench marks during the fine tuning of its optimizing phases. Other benefits were the introduction of recursive execution and a feature called a “cube stack”.

While it is possible to undo sequences of moves back to any arbitrary point, it makes more sense to simply memorize the cube’s state at key points during a solution. It is then a simple matter of restoring the cube to any of the previous states whenever a dead-end is detected. The tokens <#push> and <#pop> are used to save and restore the cube respectively. Note that these tokens are RCUBE specific; not to be confused with <push> and <pop> which are R.I.C. primitives acting on the evaluation stack.

The detection of redundant moves was central to the Naive Solution. As mentioned earlier, one can not count the turn of one slice followed by an opposing turn as a legitimate move. Likewise, over a three move sequence, undoing the first turn on the third, with no consequential second move is not allowed. An elegant method whereby such scenarios could be filtered out was developed. It involved a bit mask – a number whose binary digits represented the slices. This number would be checked and updated with each new move. Bit 0 represents the top slice. Once rotated, it is set to 1. Any subsequent turns handled by recursive invocation of the code would be inhibited from touching the same slice. Not until bit 1 (front slice) or any of the other three sides were rotated could the top once again be moved. This ensured that each successive turn did indeed further the cube’s permutations, i.e. scramble the slice in question. A more complex sequence which logically undoes itself without appearing to do so by simple inspection can not be so easily detected.

While the algorithm does indeed check whether the cube is solved at each move attempt, it was initialized with a pristine cube. This ensured that a solution would not cut short the benchmark. No actual solution is expected when starting with a solved cube within a reasonable time frame. Ultimately the cube could be restored to its starting state, which, presumably would require 2×God’s algorithm moves. The half-way point is the cube’s most scrambled state.

Below is the calling function to the Naive Solution. It sets the depth counter to five for a benchmark test. This will cause 877,032 slice turns to be executed according to the above table.