What happens if a modern constraint satisfaction and optimization program decides to play a Video Game Classic?Continue reading
Abstract: Subway shuffle is an addicting puzzle game created by Bob Hearn. It is played on a graph with colored edges that represent subway lines; colored tokens that represent subway cars are placed on the nodes of the graph. A token can be moved from its current node to an empty one, but only if the two nodes are connected with an edge of the same color of the token. The aim of the game is to move a special token to its final target position. We prove that deciding if the game has a solution is PSPACE-complete even when the game graph is planar.
The 20 white tiles are identified with their black dots; for example (2,2,0) represents the tile with two black dots in the first and second corner and zero dots on the third.If the solution says put tile (1,2,3) on face [11,12,7], then you must put the white tile on the bottom-left face, and rotate it until 1 black dot is on yellow pin 11, 2 black dots are on yellow pin 12 and 3 black dots are on yellow pin 7. You can also generate a random yellow pins configuration clicking “Random IcoSoKu”.