RCUBE (Rubik’s Cube Notation)

An interpretive language / notation for describing Rubik's Cube moves. It is used to put into practice solving algorithms.

Background

I was never a “cuber” – not ever being able to solve the thing. To me, the puzzle did not provide the necessary positive feedback nor sufficient instant gratification. Too many moves and not enough discernible progress towards the solution. Any errors made along the way would not be detected until the end of the move sequence. I had no ambition to learn by wrote any number of solutions published in the early eighty’s.

During a particularly unstimulating contract during September and October 1995 I decided to once again tackle the Rubik’s Cube problem. Fifteen years earlier I briefly explored some proof-of-concept timings using APL on a micro computer. At that time the best move rate turned out to be around 50 per second. This was too discouraging. By contrast, today’s computers achieve 1,000,000 moves per second even when executed through the interpreter described here. Now there’s hope.

The Problem

This time, the attack was to encompass all aspects of the problem. There are many. Primarily, it was to be able to solve the cube. For a model I turned to a book “The Simple Solution to Rubik’s Cube” 1981, by James G. Nourse. I reasoned that if this book, as many others, is able to convey unambiguous instruction, then it must necessarily use a self-consistent notation. This permeated several levels: the definition of cube characteristics (facets, cubets, colours), the moves (turns, layers), and the macro language that described them in a algorithmic fashion.

To be implemented however, several subgoals needed addressing. Internal cube representation, and move sequence notation at opposite sides of the spectrum. I started with a List of Goals. The book’s instruction had to be translated into some language that a computer could deal with. During this there was some confusion on how term “cube” was used – sometimes referring to a “cubet”, sometimes to the whole entity. By-the-way, “cubet” is my invention based on face/facet. Just add a ‘t’. I think conventionally they’re called cubies. Besides mimicking the book, there was also the naive solution which in theory would exhaustively try all turns until the solution was reached. Both were sketched out in a combination of pseudo code and flow charts.

A quick survey of computer languages proved none provided a close enough analog to Rubik’s Cube popular notation for move sequences. It either had to be a complex collection of “C” procedures hardwired together and recompiled for each initial scrambled cube, or some interpreter capable of receiving notation and still be reasonably fast. APL, with coaxing, could support a free-form notation of assembled functions. But again, the fact that the book already had a notation begged the question: why can’t a computer just understand the notation as is?

Rubik’s Language

Thus, RCUBE was born. It is a notation which as closely as possible resembled the book’s conventions. It also required some conditional constructs including a form of “switch” statement. So the challenge was to come up with something that offered both without looking like a patchwork – in short a new, elegant language. Immediately it was obvious that the power of this special purpose notation can be judged by how well it could be adapted to other future projects. In parallel, the encompassing language R.I.C. (Reduced Incremental Compiler) was designed. RCUBE would thus be a working subset of macro definitions and specialty tokens tailored for the puzzle. It served as proof-of-concept for R.I.C., another project that had been in the back of my mind for years.

R.I.C. was never fully defined in the process. It merely served as a framework. Essentially the concept consisted of a user definable language based on a minimal set (hence “Reduced”) of primitives to build tools towards a solution. This concept is not new; Smalltalk has similar ambition. The “Incremental Compiler” portion emphasized the optimization phase that would, through dynamic execution profiling, generate machine code where profitable.

The entire project proved to be the most difficult programming task in my career. The difficulty lies in the wide open (non existent) specs. All of the various pieces from internal representation to notation conversion had to work perfectly before the concept could be proved successful. That was an awful lot of planning. About three weeks of notes and mental exercises prior to laying down any code. This was unprecedented. I alternated between writing small fragments in Intel assembler to turn cube layers, and defining what faces and colours really meant. There had not been a task prior that had been so comprehensive in spanning the entire gamut of problem solving; from low-level to abstract-level.

The design of a new computer language seems at first to be a project most free of restrictions, and hence should be an easy task. But a quick look at existing languages and their inherent shortcomings and the desire not to make the same mistakes quickly brought this notion back into perspective. Every potential “feature” had to be evaluated. How will they affect existing elements? Or, instead, are the other elements all wrong? No compromises were allowed at this early stage. If a week of possible notation work is proved unworkable, it’s thrown out before it’s too late and committed to computer. At each stage the Book’s Solution and the Naive Solution were re-written to comply with the new improved syntax. Remaining pseudo-code fragments gradually gave way to real syntax. The two programs would later serve as benchmark suites as the working interpreter is optimized. Extracting efficiencies deep down would sometimes percolate up and cause syntax changes. So the design process was both top-down and bottom-up at the same time.

Notation of Moves

Working from just one book about the cube’s solution has the possible side-effect of inflexible notation. This was countered early by recognizing that R.I.C. needs a “macro” capability, like the preprocessor phase which handles “C”’s “#define” statements. Luckily this separate syntax structure was not deemed necessary in the end. While R.I.C.’s interpreting environment would deal with the intricacies of multi-pass conversion, there was no reason why macros would need to have a notation any different from regular function definitions. For example, if the bottom slice of the cube is called ‘B’ (bottom) or ‘D’ (down), why not just define a function called ‘B’ or ‘D’ embedded within the algorithmic solution? These macro functions must expand prior to other processing, but that’s for the run-time executer to sort out. Syntactically, the programmer should not have to cater to the idiosyncrasies of a compiler’s separate phases, in my humble opinion.

Table

Given the two popular notations above, plus possibly others, R.I.C. had to have primitives to which they are to be mapped.

R.I.C. and RCUBE primitives, or tokens, are to have the form:

<token-name>



 

Note: any resemblance to HTML entities is coincidental. The R.I.C. notation was based on syntax found in language manuals of the mainframe computer I used at that time. Angle brackets enclose syntactical elements.

This is a list of primitive tokens referencing the cube.

Other Useful Primitive Tokens

Token NameMeaning
<#color>Enquire the colour of a facet
<#display>Turn On/Off graphic display
<#history>Turn On/Off move-history
<#pop>Recall cube state
<#push>Store cube state
<#restore>Make cube pristine
<#solved>Ask if it’s solved
<#turn>Make a move
<#undo>Back-up a move
<#zeromoves>Reset moves counter

With the above rotation, facet, and additional tokens it’s almost possible to construct algorithms to maniplate Rubik’s Cube. There are a few more elements which provide conditional execution and support counters and loops required for an automated solver.

 The following language elements are more general in scope.

Token NameMeaning
&and
|or
+add
-subtract
=check if equal
<check if greater
>check if less
#not
:define label
{ ... }define function
[ ... ]conditional block
//comment
<pop>
<push>
<copy>
<copyi>
<stack>
<return>

Work in progress.

Revised 21 Aug 2020