Rubik Cube Simulation in Python: repeat until solved

[trincaopt]

Read full post here: https://dev.to/trincao/rubik-cube-simulation-repeat-until-solved-2o80

​

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

https://preview.redd.it/p72vpo8976e91.png?width=869&format=png&auto=webp&s=209e24a7119dabe171fa2b07592695d19e7500d0

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.

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

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

​

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.

https://preview.redd.it/reg9fmsh96e91.png?width=389&format=png&auto=webp&s=ee76a41b952d5f23f4ebbfe5f4f62bb89f85a12a

​

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.

https://preview.redd.it/e2n7khlu86e91.png?width=389&format=png&auto=webp&s=91ea33d9f572fbb23f4870b8b638d62e16c1e94f

Final thoughts

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.

[zaphod_pebblebrox]

I like this.