My favorite class in college was a class on Motion Planning, and I remember using the Rubik's cube as an analogy for discrete motion planning problems. It was a

My favorite class in college was a class on Motion Planning, and I remember using the Rubik's cube as an analogy for discrete motion planning problems. It was a fun way to talk about some of the less common graph search techniques, like iterative deepening. It's also interesting how the graph produced by the transitions of a Rubik's cube is so large, yet so uniform. There are 43 quintillion states, yet each state has the exact same number of transitions: 3 for each face, so 18 in total. And the fact that we actually can reliably search that space even using a relatively dumb graph search algorithm is astounding.