This game has two players, Spoiler and Solver. We start with a solved 3x3x3 rubik's cube (to make the problem easier).

Solver and Spoiler take turns making 90 degree twists (starting with Solver). The cube is forbidden from ever repeating a position (besides the start position). This guarantees the game is finite.

If at any point (besides the beginning), the rubik's cube is in a solved state, Solver wins. If the game ends before that (because a position is entered with no valid moves), Spoiler wins.

An example game would be F,F;F,F (using basic rubik's cube notation). Solver wins this game. If a game goes through each position that is one move away from the solved state, and afterwards goes to some unsolved state, Spoiler will win (since it is now impossible to get to the solved state).

So, which player has the winning strategy?

EDIT: It may be simpler to consider the same problem with the 15 puzzle first.

1more comments