DEV Community

Gonçalo Trincão Cunha
Gonçalo Trincão Cunha

Posted on

Rubik Cube Simulation in Python: repeat until solved

If you repeat any sequence of moves on a Rubik cube enough times, the cube will return to the initial (solved) state.
This happens no matter how simple or complex is the chosen sequence.

Each sequence has a length (number of moves in the sequence) and a period, or group order, which is the number of times it must be repeated until the cube returns to the solved state.

Example sequence : F' L' F' L

Sequence

Sequence Period: How many times to repeat?

On a 3x3x3 cube, depending on the sequence chosen, the period may be as low as 1 or as high as 1260. Here are a few examples.

Period Sequence
1 L L'
2 R, D, F, F, D', R'
4 U
5 F' L' F' L
6 R' D' R D
105 U', R'
1260 R' U' R D D U' F R

On a 4x4x4 cube, the periods can be much larger even reaching 765765.
Some examples.

Period Sequence
1 L L'
4 U
6 R' D' R D
80 2L Bw
12240 Rw, U, Fw, Bw, F
765765 R R Rw Uw Dw Dw

Analysis of the Sequence Period

Main question: Given a random sequence of N moves what is the average sequence period?

Although there are mathematical approaches to answer this question, we're using a simulation approach with the Python library magiccube, which is a fast Rubik Cube simulator.

The simulation is run 1000 times. Each run executes the sequence until the cube returns to the original state.

cube = magiccube.Cube(3)

# Run the simulation N times
for n in range(1000):
    # Generate a random sequence
    moves = cube.generate_random_moves(num_steps=int(sys.argv[1]))
    cube.reset()

    # Execute the sequence
    for i in range(1,1000000):
        cube.rotate(moves)
        # Check if the cube is finished
        if cube.is_done():
            print(i)
            break
Enter fullscreen mode Exit fullscreen mode

Sequence Period decay

The distribution of sequence periods has an exponential decay. Most sequences have small periods, few sequences have large periods.

Using a sequence length of 30 random moves on a 3x3x3 cube, we can see the distribution of period sizes.

Histogram

Sequence length vs period

The sequence period is typically smaller for shorter sequence lengths, but after a certain threshold, the period doesn't increase any more.
On the 3x3x3 cube, the threshold is around 2-5 moves.
On the 4x4x4 cube, the threshold is around 11-16 moves.
On the 5x5x5 cube, the threshold is in excess of 20 moves.

Sequence length vs period

Final thoughts

Hope you enjoyed.
If you are a fan of the Rubik cube, you can use the open source Python library magiccube to solve the cube and perform simulations.

Top comments (0)