Solving Rubik's cube can be thought of as a Planning problem which has :
- a state space $S$
- a set $G \subseteq S$ of goal states (in this case singleton)
- actions $A(s) \subseteq A$ applicable in each states in $S$
- action costs $c(a, s)>0$ (optional)
- discount factor $\gamma$ (optional)
On the other hand a MDP has an extra point:
- transition probabilities $P_a(s'|s)$ for $s\in S$ and $a\in A(s)$
So can solution to Rubik's cube be seen from the point of view of Markov Decision Process ? What are the practical problems where principles of solving Rubik's cube can be applied ?