Skip to main content
added 311 characters in body
Source Link

Not an answer, but just a thought or two about the problem. With the quarter turn metric the Cayley graph is a 12-regular graph. Every element in the Rubik's group can be assigned a "rank", the value of the smallest number of moves to get back to the origin. By making a parity argument, we can see that a quarter turn (move on the Cayley graph) always changes this number by 1 or -1. So we could arrange the Cayley graph like a Hasse diagram.

I think understanding the size of the various levels (not sure if that's the term, but the collection of elements having the same minimum solve number) might be key to understanding any strategy for either player. For example on the first turn the state of the cube is at level 1. The Solver can't undo this move and will be forced to move to level 2. The Spoiler clearly wouldn't move the state back to level 1, so moves up to 3. I think a naive strategy for the Spoiler might be to try to move the puzzle up in level all the time. There are more level 3 states than level 2 states, so (being generous with the symmetry and structure of the Cayley graph) I suspect he can move to enough level 3 states any time the puzzle return to a level 2 state and exhaust the level 2 possibilities for the Solver, thus shutting the Solver off from victory.

This is just my initial thoughts. I will update if I think of something more, or if the structure of the Cayley graph turns out to be structured in such a way as to stop this strategy. Let me know if anyone manages to build off this idea.

EDIT: According to https://www.cube20.org/qtm/, the largest sized level is at 21. Being odd, these are states the Spoiler moves the puzzle to. I think that if the Spoiler tries to keep the puzzle at 21, then he might be able to exhaust the 20 level or the 22 level, before the level 21 states are exhausted.

Not an answer, but just a thought or two about the problem. With the quarter turn metric the Cayley graph is a 12-regular graph. Every element in the Rubik's group can be assigned a "rank", the value of the smallest number of moves to get back to the origin. By making a parity argument, we can see that a quarter turn (move on the Cayley graph) always changes this number by 1 or -1. So we could arrange the Cayley graph like a Hasse diagram.

I think understanding the size of the various levels (not sure if that's the term, but the collection of elements having the same minimum solve number) might be key to understanding any strategy for either player. For example on the first turn the state of the cube is at level 1. The Solver can't undo this move and will be forced to move to level 2. The Spoiler clearly wouldn't move the state back to level 1, so moves up to 3. I think a naive strategy for the Spoiler might be to try to move the puzzle up in level all the time. There are more level 3 states than level 2 states, so (being generous with the symmetry and structure of the Cayley graph) I suspect he can move to enough level 3 states any time the puzzle return to a level 2 state and exhaust the level 2 possibilities for the Solver, thus shutting the Solver off from victory.

This is just my initial thoughts. I will update if I think of something more, or if the structure of the Cayley graph turns out to be structured in such a way as to stop this strategy. Let me know if anyone manages to build off this idea.

Not an answer, but just a thought or two about the problem. With the quarter turn metric the Cayley graph is a 12-regular graph. Every element in the Rubik's group can be assigned a "rank", the value of the smallest number of moves to get back to the origin. By making a parity argument, we can see that a quarter turn (move on the Cayley graph) always changes this number by 1 or -1. So we could arrange the Cayley graph like a Hasse diagram.

I think understanding the size of the various levels (not sure if that's the term, but the collection of elements having the same minimum solve number) might be key to understanding any strategy for either player. For example on the first turn the state of the cube is at level 1. The Solver can't undo this move and will be forced to move to level 2. The Spoiler clearly wouldn't move the state back to level 1, so moves up to 3. I think a naive strategy for the Spoiler might be to try to move the puzzle up in level all the time. There are more level 3 states than level 2 states, so (being generous with the symmetry and structure of the Cayley graph) I suspect he can move to enough level 3 states any time the puzzle return to a level 2 state and exhaust the level 2 possibilities for the Solver, thus shutting the Solver off from victory.

This is just my initial thoughts. I will update if I think of something more, or if the structure of the Cayley graph turns out to be structured in such a way as to stop this strategy. Let me know if anyone manages to build off this idea.

EDIT: According to https://www.cube20.org/qtm/, the largest sized level is at 21. Being odd, these are states the Spoiler moves the puzzle to. I think that if the Spoiler tries to keep the puzzle at 21, then he might be able to exhaust the 20 level or the 22 level, before the level 21 states are exhausted.

Source Link

Not an answer, but just a thought or two about the problem. With the quarter turn metric the Cayley graph is a 12-regular graph. Every element in the Rubik's group can be assigned a "rank", the value of the smallest number of moves to get back to the origin. By making a parity argument, we can see that a quarter turn (move on the Cayley graph) always changes this number by 1 or -1. So we could arrange the Cayley graph like a Hasse diagram.

I think understanding the size of the various levels (not sure if that's the term, but the collection of elements having the same minimum solve number) might be key to understanding any strategy for either player. For example on the first turn the state of the cube is at level 1. The Solver can't undo this move and will be forced to move to level 2. The Spoiler clearly wouldn't move the state back to level 1, so moves up to 3. I think a naive strategy for the Spoiler might be to try to move the puzzle up in level all the time. There are more level 3 states than level 2 states, so (being generous with the symmetry and structure of the Cayley graph) I suspect he can move to enough level 3 states any time the puzzle return to a level 2 state and exhaust the level 2 possibilities for the Solver, thus shutting the Solver off from victory.

This is just my initial thoughts. I will update if I think of something more, or if the structure of the Cayley graph turns out to be structured in such a way as to stop this strategy. Let me know if anyone manages to build off this idea.