# What is God's Number for WrapSlide?

First let me describe WrapSlide:

The main puzzle is a 6x6 grid of colored 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. 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 color goes into which quadrant)

A more detail description of the puzzle and screenshots can be found here:

http://nontrivialgames.blogspot.com/2014/05/wrapslide-review.html

It can also be downloaded for free for Apple and Android devices here:

https://itunes.apple.com/app/wrapslide/id795712935?mt=8

https://play.google.com/store/apps/details?id=com.wrapslide.android.wrapslide

Some info:

WrapSlide has roughly half the number of configurations that Rubik's Cube have: 36!/(9!9!9!9!) = 21452752266265320000. (It was proven by two Dutch students that all states are reachable from the unmixed state)

God's number for WrapSlide is at least 21. I think I was lucky to find this state 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

An upper bound is 31, because any one color can always be fixed in 12 moves (or less), and 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.

## Comment viewing options

### WrapSlide SM Histogram

I now have data for the optimal solution of 700 random states and can firm up the depth distribution.

**WrapSlide SM Metric Histogram: 700 Random Tableaux**

Depth | Count | Fraction |

20 | 1 | 0.1% |

21 | 1 | 0.1% |

22 | 11 | 1.6% |

23 | 46 | 6.6% |

24 | 124 | 17.7% |

25 | 266 | 38.0% |

26 | 221 | 31.6% |

27 | 30 | 4.3% |

28 | 0 |

The previously reported depth 27 tableau is wrong—it is at depth 26. Here is a depth 27 state:

State 1 0 0 1 3 1 0 2 3 1 0 2 3 1 3 2 3 3 3 1 2 1 0 3 0 0 2 2 1 2 1 0 3 1 2 0 2 Depth: 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Solution: UL LD RU UR RU UL LU LU LU UR RU UL RD DL RU UL RU UL DR LU DR LD RU UR LU DR LD Time: 03:43:20.17

### confirmation

I confirm MacKenzie's numbers for depths up to 7 for the 20 moves case, and for depths up to 9 for the 8 moves case. I also took each one level deeper.

20 moves case 8 moves case distance pos cumulative pos cumulative 0 1 1 1 1 1 8 9 8 9 2 80 89 40 49 3 784 873 224 273 4 7612 8485 1236 1509 5 73500 81985 6680 8189 6 705652 787637 35800 43989 7 6750300 7537937 189480 233469 8 64638710 72176647 997544 1231013 9 5243650 6474663 10 27581964 34056627

What I find interesting is that at these new depths, the branching factor actually increased slightly.

### Branching

Thanks Bruce. It's always good to have independent corroboration. The business of the branching factor is curious. I would expect them to decrease steadily. Using symmetry reduction I have extended the calculation out a bit further:

Depth | Eq Classes(sm) | Cosets(sm) | Branch | Eq Classes(mm) | Cosets(mm) | Branch |

0 | 1 | 1 | 1 | 1 | ||

1 | 1 | 8 | 8.000 | 1 | 8 | 8.000 |

2 | 3 | 40 | 5.000 | 5 | 80 | 10.000 |

3 | 9 | 224 | 5.600 | 33 | 784 | 9.800 |

4 | 49 | 1,236 | 5.518 | 269 | 7,612 | 9.709 |

5 | 229 | 6,680 | 5.405 | 2,390 | 73,500 | 9.656 |

6 | 1,179 | 35,800 | 5.359 | 22,368 | 705,652 | 9.601 |

7 | 6,073 | 189,480 | 5.293 | 211,997 | 6,750,300 | 9.566 |

8 | 31,636 | 997,544 | 5.265 | 2,023,698 | 64,638,710 | 9.576 |

9 | 165,180 | 5,243,650 | 5.257 | 19,384,818 | 619,929,750 | 9.591 |

10 | 865,427 | 27,581,964 | 5.260 | |||

11 | 4,548,685 | 145,252,396 | 5.266 | |||

12 | 23,954,413 | 765,701,746 | 5.272 |

Indeed, the branching factors actually creep up. This is perhaps because a coset space needn't have the uniformity of the more familiar state space of a group.

### mm calculations confirmed

Depth Eq Classes(mm) Cosets(mm) 0 1 1 1 1 8 2 5 80 3 33 784 4 269 7,612 5 2,390 73,500 6 22,368 705,652 7 211,997 6,750,300 8 2,023,698 64,638,710 9 19,384,818 619,929,750 10 186,025,530 5,951,538,148

### The Size of the Problem

I've played around with WrapSlide enough to get a sense of the constraints involved.

The WrapSlide puzzle consists of a 6 x 6 grid of tokens in four different colors. In the solved puzzle the nine tokens in each of the four quadrants of the tableau are of the same color. It doesn't matter which color is solved to which quadrant.

To model the puzzle mathematically we start by representing the state of the puzzle as an element of the S36 permutation group. The permutation lists which of
the 36 tokens is in each puzzle position. There are 36! = 3.7 x 10^{41} different permutations of the token positions.

In the solved position the tokens of the same color may be swapped around and the puzzle is still solved. Also, all the tokens of one color may be swapped with all tokens of a second
color and the puzzle remains in a solved condition. Thus there are (9!)^{4} * 4! = 4.2 x 10^{23} token permutations which represent the
puzzle in a solved condition. These permutations form a subgroup of the S36 group, Se, which will be called the identity subgroup. The distinct states of the puzzle map to the left
cosets of the identity subgroup:

g * Se where g is an element of the S36 group

If one thinks of g as a sequence of moves, it doesn't matter to which of the 4.2 x 10^{23} solved positions the sequence is applied the result is essentially the same
puzzle position. The number of distinct positions for the puzzle is then the number of Se cosets:

36! / ( (9!)^{4}* 4! ) = 893,864,677,761,055,000

In designing an optimal solver for the puzzle the obvious starting point is the sub-task of solving one of the four colors. There are 36! / (27! * 9!) = 94,143,280 arrangements of the tokens of one color. An efficient IDA solver needs two look-up tables, a depth table and a move table. The depth table lists the depths of each of the 94,143,280 one color configurations and the move table lists the actions of the puzzle moves on these configurations. For the WrapSlide puzzle the constraining factor is the size of the move table. In my model with eight generators the size of the move table is:

94,143,280 positions * 8 generators * 4 bytes per entry = 3,012,584,960 byte move table

With a nearly 3 GB move table we've reached the limit of today's desktops. I see no prospect of increasing the speed of my solver with a deeper depth table. There simply isn't the memory this would require. And my solver takes upward of an hour to solve a random position. As far as I can see, I think that finding the diameter of the WrapSlide puzzle would be at least as hard as finding the diameter of Rubik's cube.

### How long?

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

(That is the one I found that has distance 21 (multi-position move metric). And how many moves does it take for the sm metric?

### Is God's number for WrapSlide the same as the diameter?

Is the same true for WrapSlide? That is, has every state some other states that are the diameter away? My problem is that for the cube, every move takes you to ANOTHER state, because each element of the group/graph represents a DIFFERENT arrangement of the cubies. For WrapSlide there are states that when you make a move, the state still looks the same. For example, if I move the right 2 down in this configuration:

000 111

000 222

000 111

333 222

333 111,

it still looks the same. So my argument to remap my graph when reordering stickers fail, because for my original graph all states look different, but when relabelling there might be problems with states going to themselves.

In short: Is there an easy way to see that when determining the diameter of WrapSlide, I only have to determine the longest distance from the unmixed states? Or might there actualy be two other states that are further away from each other?

### Good point. Since we're deal

Good point. Since we're dealing with a coset space rather than a group, I may have misused the term diameter. Is it possible that two cosets are farther from one another than the distance the deepest coset is from the identity subgroup? I don't know. I'll have to think about that.

Your position is at depth 26 in the single shift metric:

Tableau: 0 0 0 2 0 2 1 2 1 2 3 1 0 3 0 2 0 2 1 3 1 3 3 3 1 0 2 2 1 2 1 3 1 3 0 3 2014-10-30 07:21:01.510 PerPuzzle[4304:440912] Start Solution 2014-10-30 07:43:08.801 PerPuzzle[4304:440912] Solution Found: 26 moves UL RD UR DR LD DR DR LD UL LD RD DR DR RD DR LU UL DL DL LU LU UL DR LU DR RD UL: shift the upper ranks to the left; LU: shift the left files up, etc.

### Cayley Graphs

I thought about it and, no, for a coset space one can't assume that the depth of the deepest position from the solved configuration is the actual diameter of the coset space. As a case in point I did the configurations at depth calculation for the WrapSlide tokens of one color starting from a random configuration. As you can see the depth distribution is totally different. From this position the deepest position is at depth 13 while from a solved configuration the deepest configuration is at depth 17. It is possible that there could be a position from which the deepest configuration would be greater than 17. In contrast I did a states at depth calculation for the 2x2x2 Cube and got the same distribution starting from a random state as that starting from identity. For a group the Cayley graph must be symmetric wrt all nodes since all elements of a group are symmetries, i.e. g * G = G. For a coset space that is not true.

WrapSlide | 2x2x2 Cube | |||||

Depth | From Identity | From Random | Depth | From Identity | From Random | |

0 | 4 | 4 | 0 | 1 | 1 | |

1 | 16 | 28 | 1 | 6 | 6 | |

2 | 64 | 160 | 2 | 27 | 27 | |

3 | 368 | 894 | 3 | 120 | 120 | |

4 | 1,840 | 4,838 | 4 | 534 | 534 | |

5 | 8,272 | 25,570 | 5 | 2,256 | 2,256 | |

6 | 35,200 | 131,022 | 6 | 8,969 | 8,969 | |

7 | 147,160 | 647,444 | 7 | 33,058 | 33,058 | |

8 | 571,688 | 3,001,300 | 8 | 114,149 | 114,149 | |

9 | 2,034,216 | 12,224,740 | 9 | 360,508 | 360,508 | |

10 | 6,385,460 | 35,855,242 | 10 | 930,588 | 930,588 | |

11 | 16,378,200 | 38,767,987 | 11 | 1,350,852 | 1,350,852 | |

12 | 29,969,260 | 3,483,660 | 12 | 782,536 | 782,536 | |

13 | 29,227,028 | 391 | 13 | 90,280 | 90,280 | |

14 | 8,987,776 | 14 | 276 | 276 | ||

15 | 395,504 | |||||

16 | 1,220 | 3,674,160 | 3,674,160 | |||

17 | 4 | |||||

94,143,280 | 94,143,280 |

### Single Position Shift Metric

I've got my implementation of WrapSlide put together in rough form. This includes an optimal solver. This is written for an eight move generator set which only includes the moves which roll the tiles one position. The IDA solver prunes by the sub-problem of solving the red tokens. In the 8 generator metric the depth table looks like:

Depth table for configurations of the Red tokens2014-10-25 13:51:59.656 PerPuzzle[1255:73689] 0 4 4 2014-10-25 13:51:59.829 PerPuzzle[1255:73689] 1 16 20 2014-10-25 13:52:00.007 PerPuzzle[1255:73689] 2 64 84 2014-10-25 13:52:00.180 PerPuzzle[1255:73689] 3 368 452 2014-10-25 13:52:00.352 PerPuzzle[1255:73689] 4 1840 2292 2014-10-25 13:52:00.525 PerPuzzle[1255:73689] 5 8272 10564 2014-10-25 13:52:00.703 PerPuzzle[1255:73689] 6 35200 45764 2014-10-25 13:52:00.893 PerPuzzle[1255:73689] 7 147160 192924 2014-10-25 13:52:01.117 PerPuzzle[1255:73689] 8 571688 764612 2014-10-25 13:52:01.459 PerPuzzle[1255:73689] 9 2034216 2798828 2014-10-25 13:52:02.166 PerPuzzle[1255:73689] 10 6385460 9184288 2014-10-25 13:52:03.799 PerPuzzle[1255:73689] 11 16378200 25562488 2014-10-25 13:52:07.151 PerPuzzle[1255:73689] 12 29969260 55531748 2014-10-25 13:52:12.137 PerPuzzle[1255:73689] 13 29227028 84758776 2014-10-25 13:52:16.763 PerPuzzle[1255:73689] 14 8987776 93746552 2014-10-25 13:52:18.594 PerPuzzle[1255:73689] 15 395504 94142056 2014-10-25 13:52:18.872 PerPuzzle[1255:73689] 16 1220 94143276 2014-10-25 13:52:19.047 PerPuzzle[1255:73689] 17 4 94143280

There are four elements at depth 0 since it doesn't matter into which quadrant the tiles are solved. The red tiles may be put in order in at most 17 single position moves (the "sm" metric to coin a term) and average 12sm to 13sm moves deep. By using symmetry conjugation to map the configuration of the other three tile sets onto the red tiles the same table may be used to prune by the depths all four tile sets. A position will be at least at the depth of the deepest of the four sets.

I've only solved a handful of random tableaux. The depths have ranged from 23 to 27 moves with 25 moves the most probable. The times have ranged from about a minute for a 23 move position to nearly five hours for the 27 move position. This is too long for my PerPuzzle app. I want the user to see a solution in at most 5 to 10 seconds. I'll need to put together a sub-optimal two phase solver—first solve one tile set then the complete tableau using only 4 of the 8 generators.

### PerPuzzle

### Adding WrapSlide to PerPuzzle

### Good deal, I've already start

### Another Mountain

On the face of it, with a state space of 2 x 10^{19}

To solve the puzzle do the colors have to go in their original quadrant or does simply separating the colors suffice? If the latter then the state space would be reduced by a factor of 4!.

### symmetries

Yes, simply seperarting the colors suffice when solving the puzzle.

Yes, there is a lot of symmetry: 4! color swops, and 8 ways to oriented the grid. Tom Rokicki pointed out to me there are 4 more because the puzzle fits onto a torus. (2 choices to "cut open" the torus both horizontally and vertically). I am in the process of speeding up my solver by incorperating the last four symmetries also.

My distance count for moves 0-6 (that uses all the 32 x 4! symmetries to reduce the states) is:

1

1

5

38

314

2800

26327

### mistake

1

1

5

33

269

2390

22368

(See a more complete list below "computations")

### 32 symmetries

I added the two glide plane symmetries to the 8 point group symmetries I already had and did the closure. I come up with a total of 32 symmetries. Does that sound right?

### Glide Plane

*"Tom Rokicki pointed out to me there are 4 more because the puzzle fits onto a torus. (2 choices to "cut open" the torus both horizontally and vertically)."*

Hmm, I hadn't thought of that. That type of symmetry is known as a glide plane in crystallography.

## Computations

I've completed a run of 100 random positions solved with the 8 generator solver. The most probable depth is 25 or 26 moves. The average time was a shade over 1 hr.

I've performed a breadth first cosets at depth calculation for both the 20 move metric and the 8 move metric.

These numbers need to be confirmed. The number log(N) / log( b ) where N is the total number of states and b is the branching factor is the depth at which exponential growth will exhaust the state space. The actual distribution will level off before this and max out a bit beyond. Using 9.6 as the branching factor for the 20 generator metric one gets 18.0. This jives with you're finding that the most probable depth is 19. Using 5.3 as the branching factor for the 8 generator metric the result is 24.8. This compares well with what I'm finding that the max is between depth 25 and depth 26.