Rubik’s Cube in Prolog — Order

3 min read Original article ↗

Kenichi Sasagawa

I am preparing material for a Prolog book.
As a playground for group theory, I chose the Rubik’s Cube.

I first learned that the Rubik’s Cube could be analyzed using group theory about forty years ago, from Douglas Hofstadter’s book Metamagical Themas. This time, I decided to work through it seriously using Prolog.

State Representation

For simplicity, we use a 2×2 Rubik’s Cube.

I considered how to represent the cube as Prolog data.

A cube state is defined by:

  • the positions of the 8 corner pieces
  • the orientation of each piece

The positions are numbered clockwise as 1, 2, 3, 4 on the front face, and 5, 6, 7, 8 on the back face (also clockwise when viewed from the front).

The orientation of each piece is represented as a list of three elements:

[up-down, front-back, left-right]

The initial orientation is [0,1,2].

Following the standard Rubik’s Cube notation, we describe moves using F, U, and R.

  • F rotates the front face clockwise.
  • During an F move, the up-down and left-right components of the orientation are swapped.
[0,1,2] → [1,0,2]

Similarly, the orientation changes for U and R moves are defined as:

U: [0,1,2] → [0,2,1]
R: [0,1,2] → [2,0,1]

The cube state is represented by a predicate cube/2.

The initial state is:

cube(
  [0,1,2,3,4,5,6,7],
  [[0,1,2],[0,1,2],[0,1,2],[0,1,2],
   [0,1,2],[0,1,2],[0,1,2],[0,1,2]]
).

Describing Moves

Based on this representation, the F move can be written in Prolog as follows:

% F turn (clockwise looking at F face)
movef([P1,P2,P3,P4,P5,P6,P7,P8],
      [[O1ud,O1lr,O1fb],[O2ud,O2lr,O2fb],
       [O3ud,O3lr,O3fb],[O4ud,O4lr,O4fb],O5,O6,O7,O8],
      [P4,P1,P2,P3,P5,P6,P7,P8],
      [[O4lr,O4ud,O4fb],[O1lr,O1ud,O1fb],
       [O2lr,O2ud,O2fb],[O3lr,O3ud,O3fb],O5,O6,O7,O8]).

One advantage of Prolog is bidirectional computation.
The inverse of the F move requires no special definition — simply reversing the arguments allows the same predicate to be used.

Repeating a Move N Times

Next, I examined what happens when the F move is applied repeatedly.

% cube state
initial_cube(
  cube([0,1,2,3,4,5,6,7],
       [[0,1,2],[0,1,2],[0,1,2],[0,1,2],
        [0,1,2],[0,1,2],[0,1,2],[0,1,2]])
).
% iteration N times of move M
iterate(N,M,C1) :-
    initial_cube(C),
    iterate1(N,M,C,C1).iterate1(0,M,C,C).
iterate1(N,M,cube(P,O),C) :-
    Pred =.. [M,P,O,P1,O1],
    call(Pred),
    N1 is N-1,
    iterate1(N1,M,cube(P1,O1),C).

Let’s try it:

?- iterate(1,movef,C).
C = cube([3,0,1,2,4,5,6,7],
         [[1,0,2],[1,0,2],[1,0,2],[1,0,2],
          [0,1,2],[0,1,2],[0,1,2],[0,1,2]]).
yes
?- iterate(2,movef,C).
C = cube([2,3,0,1,4,5,6,7],
         [[0,1,2],[0,1,2],[0,1,2],[0,1,2],
          [0,1,2],[0,1,2],[0,1,2],[0,1,2]]).
yes?- iterate(3,movef,C).
C = cube([1,2,3,0,4,5,6,7],
         [[1,0,2],[1,0,2],[1,0,2],[1,0,2],
          [0,1,2],[0,1,2],[0,1,2],[0,1,2]]).
yes?- iterate(4,movef,C).
C = cube([0,1,2,3,4,5,6,7],
         [[0,1,2],[0,1,2],[0,1,2],[0,1,2],
          [0,1,2],[0,1,2],[0,1,2],[0,1,2]]).
yes

After four repetitions, the cube returns to the initial state.
This matches our intuition: rotating a face four times brings it back.

Order

In group theory, this concept is called the order of an operation.

The order of an operation is the number of times it must be applied to return to the identity (initial state).

Here is the Prolog code to compute the order:

% order of operation M
order(M,N) :-
    initial_cube(C),
    order1(0,N,M,C,C).
order1(N,N,M,C,C) :-
    N > 0.
order1(N,N2,M,C,cube(P,O)) :-
    Pred =.. [M,P,O,P1,O1],
    call(Pred),
    N1 is N+1,
    order1(N1,N2,M,C,cube(P1,O1)).

Testing it:

?- order(movef,N).
N = 4.
yes

The F move has order 4, exactly as expected.

Composite Moves

Now let us define U, R, and composite moves such as F-U-R.

% U turn
moveu([P1,P2,P3,P4,P5,P6,P7,P8],
      [[O1ud,O1lr,O1fb],[O2ud,O2lr,O2fb],O3,O4,
       [O5ud,O5lr,O5fb],[O6ud,O6lr,O6fb],O7,O8],
      [P5,P1,P3,P4,P6,P2,P7,P8],
      [[O5ud,O5fb,O5lr],[O1ud,O1fb,O1lr],O3,O4,
       [O6ud,O6fb,O6lr],[O2ud,O2fb,O2lr],O7,O8]).
% R turn
mover([P1,P2,P3,P4,P5,P6,P7,P8],
      [O1,[O2ud,O2lr,O2fb],[O3ud,O3lr,O3fb],O4,
       O5,[O6ud,O6lr,O6fb],[O7ud,O7lr,O7fb],O8],
      [P1,P6,P2,P4,P5,P7,P3,P8],
      [O1,[O6fb,O6lr,O6ud],[O2fb,O2lr,O2ud],O4,
       O5,[O7fb,O7lr,O7ud],[O3fb,O3lr,O3ud],O8]).

Composite moves:

movefur(P,O,P3,O3) :-
    mover(P,O,P1,O1),
    moveu(P1,O1,P2,O2),
    movef(P2,O2,P3,O3).
moveruf(P,O,P3,O3) :-
    movef(P,O,P1,O1),
    moveu(P1,O1,P2,O2),
    mover(P2,O2,P3,O3).movefru(P,O,P3,O3) :-
    moveu(P,O,P1,O1),
    mover(P1,O1,P2,O2),
    movef(P2,O2,P3,O3).

Checking their orders:

?- order(moveu,N).
N = 4.
yes
?- order(mover,N).
N = 4.
yes

Again, this matches intuition.

But what about composite moves?

?- order(movefur,N).
N = 18.
yes
?- order(moveruf,N).
N = 30.
yes?- order(movefru,N).
N = 30.
yes

What Do 18 and 30 Mean?

These numbers mean that applying the composite move 18 or 30 times returns the cube to the original state.

This may seem mysterious at first, but it is a natural consequence of group theory.
It is related to Lagrange’s theorem, which states that the order of an element divides the order of the group.

Fascinating!

Conclusion

Mathematics is truly fun.
Using Prolog, we can actually compute and verify abstract group-theoretic concepts.

The full code is included in the tests folder of N-Prolog.

Mathematics is super fun!