Rubik's Cube Solver

[ssoelvsten]

Watching Sebastian Lague's recent video on solving a 3x3 rubik's cube, I thought this might be an interesting little problem for a symbolic approach. It very nicely maps to the reachability analysis of an initial and target state via a transition relation.

Inputs:

• Generate a random initial state (given the size of the cube).
• Output the generated initial state.
• Parse a cube from a simple file.

Symbolic Reachability Analysis

• Encode the state of the cube in a binary number. Based on my experience with 2D problems, the 3D nature of this problem will probably make it hard to have the BDD not explode. My best initial guess is to encode the colour of each face in 3 adjacent variables.
• Forward Search (for a 3x3 cube, this is bounded to a depth of 20)
• Forward and Backward Search (also search backwards from the solved state)

[ssoelvsten]

Useful Reading

• https://link.springer.com/article/10.1007/s10009-005-0191-z
• https://link.springer.com/chapter/10.1007/978-3-642-21581-0_9
• Studies on Permutation Set Manipulation Based on Decision Diagrams
• https://arxiv.org/abs/1706.06708

This problem seems to either lend itself to an interesting use of ZDDs or to even suggest implementing a new (ZDD-based?) decision diagram.