# What is God's number for the WrapSlide puzzle?

WrapSlide is a slide-puzzle (reminding of Rubik's Cube) consisting of a 6x6 grid of coloured tiles which are separated into four quadrants of 3x3 tiles. When it is unmixed all the tiles in a quadrant have the same colour. A move consists of sliding either the top, bottom, left or right two quadrants of tiles 1 to 5 units horizontally or vertically (tiles wrap around when moved). Stated differently, a move consists of sliding either the top, bottom, left of right half (consisting of 3 rows or 3 columns) relative to the other half, thus giving 4x5 possible moves to choose from. As with Rubik's cube the puzzle is to return it to its unmixed state after it is scrambled. (For the unmixed state we don't care which colour goes into which quadrant).

See this review on the puzzle for screen-shots and more detail.

God's Algorithm refers to any algorithm which produces a solution to this type of puzzle having the fewest possible number of moves. God's Number for WrapSlide would be the number of moves this algorithm would take in the worst case to solve the WrapSlide puzzle.

A lower bound is 21, since there is one configuration known (so far), that can't be solved in 20 moves:

0 0 0 3 0 3
2 3 2 3 1 2
0 1 0 3 0 3
2 1 2 1 1 1
2 0 3 3 2 3
2 1 2 1 0 1

Solving just one colour can always be done in 12 moves or less, and solving the sub-puzzle of fixing 3 colours doing (say) only left and lower moves can always be done in 19 moves. Thus giving 12+19 as an upper bound. This is a very poor upper bound, but it is a start.

• How exactly is the lower bound established? It seems too big for exhaustive search. – The Masked Avenger Oct 22 '14 at 15:27
• I built a tree, storing all states that are exactly 1,2,...,10 moves away from the unmixed state. There are 743961173 on level 10 and it can be stored in about 6GB. I only store non-isomorphic states under the 4! colour changes and 8 orientations of the grid. I then compute all the states that are exactly 1,2,...,10 moves away from the MIXED state above and check if each of these states is in level 10 of the first tree. Since no matches were found, there is no way to solve that configuration in 10+10 moves. This computation took about a week to do, but I am sure there are faster ways to do it. – Alewyn Burger Oct 23 '14 at 9:04
• Can you reach every combination of colors? Or there are some invariants --- in this case, which? – Ilya Bogdanov Oct 24 '14 at 15:00
• At least for 6x6 and 8x8 (I suspect for all but did not test) the group is the full symmetric group, so any permutation would be possible. – ahulpke Oct 24 '14 at 16:43