Home »

What is God's Number for WrapSlide?

Submitted by Alewyn Burger on Wed, 10/22/2014 - 08:36.
I developed a slide-puzzle called WrapSlide that reminds of Rubik's Cube. I am interested in determining God's number for WrapSlide. I think my initial approach is too naive and may be I should leave it to the experts.

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.
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Computations

Submitted by B MacKenzie on Tue, 11/04/2014 - 08:25.

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.

Length      Count
21              1
22              2
23              4
24             10
25             43
26             37
27              3

Random Positions Solved: 100

Average Solution Time: 1 hr 4 min 14.73 sec
Average Solution Length: 25.15

Deepest State Found:
 0 1 1 2 1 0
 1 2 0 1 0 2
 2 3 3 3 3 0
 3 0 1 0 1 0
 2 1 2 3 2 1
 3 3 2 0 3 2

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

Depth 20 Move Branch 8 Move Branch
0 1
1
1 8 8.00 8 8.00
2 80 10.00 40 5.00
3 784 9.80 224 5.60
4 7,612 9.71 1,236 5.52
5 73,500 9.66 6,680 5.40
6 705,652 9.60 35,800 5.36
7 6,750,300 9.57 189,480 5.29
8

997,544 5.26
9

5,243,650 5.26

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.

» login or register to post comments

WrapSlide SM Histogram

Submitted by B MacKenzie on Sun, 05/03/2015 - 09:46.

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
» login or register to post comments

confirmation

Submitted by Bruce Norskog on Fri, 11/07/2014 - 13:11.

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.

» login or register to post comments

Branching

Submitted by B MacKenzie on Fri, 11/07/2014 - 19:31.

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.

» login or register to post comments

mm calculations confirmed

Submitted by Alewyn Burger on Fri, 11/14/2014 - 09:02.
I get the same numbers for the mm metric. I added depth 10. 
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
» login or register to post comments

The Size of the Problem

Submitted by B MacKenzie on Wed, 10/29/2014 - 12:37.

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 1041 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 1023 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 1023 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.

» login or register to post comments

How long?

Submitted by Alewyn Burger on Thu, 10/30/2014 - 04:26.
How long does you solver take to solve this configuration:

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?
» login or register to post comments

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

Submitted by Alewyn Burger on Thu, 10/30/2014 - 04:21.
My knowledge of group theory is unfortunately not too hot. I understand diameter in terms of graph theory: every state is a vertex in the graph and two states are joined if there is a single move from one state to the other. The diameter is then the furthest two states can be from one another. I can convince myself that for EVERY state of Rubik's cube, there are some other states that are the maximum distance away. That is because you can remove stickers and stick them back as the solved pattern. So you can "remap" your graph.

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?
» login or register to post comments

Good point. Since we're deal

Submitted by B MacKenzie on Thu, 10/30/2014 - 08:19.

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.
» login or register to post comments

Cayley Graphs

Submitted by B MacKenzie on Fri, 10/31/2014 - 09:09.

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



» login or register to post comments

Single Position Shift Metric

Submitted by B MacKenzie on Mon, 10/27/2014 - 07:12.

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 tokens 
2014-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.

» login or register to post comments

PerPuzzle

Submitted by B MacKenzie on Wed, 10/22/2014 - 15:17.
I have a freeware app PerPuzzle on the Mac OS App Store. It occurred to me that this puzzle would be a good addition to the App. Would you be upset if I added an implementation of WrapSlide to my App?
» login or register to post comments

Adding WrapSlide to PerPuzzle

Submitted by Alewyn Burger on Fri, 10/24/2014 - 03:08.
I will be happy if you do that - as long as the puzzle is called WrapSlide.
» login or register to post comments

Good deal, I've already start

Submitted by B MacKenzie on Fri, 10/24/2014 - 07:37.
Good deal, I've already started on the code. I'll put in an "Available on the App Store" link to your iOS app in the docs.
» login or register to post comments

Another Mountain

Submitted by B MacKenzie on Wed, 10/22/2014 - 09:13.

On the face of it, with a state space of 2 x 1019 finding the diameter would be a monumental task. Have you done a histogram—solve say 1000 random puzzles to see what the most probable depth would be?

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!.

» login or register to post comments

symmetries

Submitted by Alewyn Burger on Fri, 10/24/2014 - 03:01.
I have a very slow solver at the moment, but when running about 40 random instances the bulk (about half) of states seem to require 19 moves.

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
» login or register to post comments

mistake

Submitted by Alewyn Burger on Fri, 11/14/2014 - 09:09.
I found a mistake in my program. The table for 0-6 moves should be:

1
1
5
33
269
2390
22368

(See a more complete list below "computations")
» login or register to post comments

32 symmetries

Submitted by B MacKenzie on Fri, 10/24/2014 - 09:22.

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?

» login or register to post comments

Glide Plane

Submitted by B MacKenzie on Fri, 10/24/2014 - 07:31.

"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.

» login or register to post comments