# Who wins the Rubik's cube game?

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.

• Now I'm wondering if this sort of game has been studied before for other groups with specified generators; is there an existing name for this sort of game? – Harry Altman Apr 21 '18 at 19:53
• @HarryAltman no idea. If you find one, let me know. A related game is the Sudoku solver spoiler game. – PyRulez Apr 21 '18 at 19:54
• You're talking about a self-avoiding walk on a Cayley graph, where each player takes turns deciding which edge to traverse from the current vertex. I like @HarryAltman's idea of looking at simpler groups first. – Jim Conant Apr 21 '18 at 20:31
• Phrased in the Cayley graph language, it maybe makes more sense not to have two different kinds of players, but just to have both players trying to keep making moves until one is unable to visit a new vertex (and thereby loses). – Sam Hopkins Apr 21 '18 at 20:50
• @SamHopkins: That's also an interesting game to play on a finite directed graph, but I think it's a different game. – Lee Mosher Apr 21 '18 at 21:56