The Rubik’s cube and discrete optimization

I’m sure you are aware of what a Rubik’s cube is, so I’m not going to go over the general description (https://en.wikipedia.org/wiki/Rubik\%27s_Cube) of this puzzle, but rather focus on the connections it has to mathematics and computer science.

If it’s not explicitly stated, by “cube” I mean the 3 × 3 × 3 classic Rubik’s cube. There are lots of variations based on the original 3 × 3 × 3 puzzle, but they are still far less popular than the classic invention.

Despite being quite simple in terms of mechanics and the task at hand, the cube is quite a tricky object in terms of all the transformations we can make by possible rotations of its sides. It was calculated that in total, the cube has ≈ 4.33 ⋅ 10¹⁹ distinct states reachable by rotating it. That’s only the states that are reachable without...