# God's Number for a Bandaged 3x3x3



## qqwref (Dec 4, 2010)

Here's a couple of known ones (in htm):
<U2,D2,R2,L2,F2,B2> - 15
<U2,R2,L2,F2,B2> - 16
<U,D,R2,L2,F2,B2> - 18?
Normal cube - 20
<U,R2> - 20
<U,R> - 20
Bandaged Cube (Bicube) - 29

Assuming (for the sake of widest reasonable search space) that bandaging a puzzle includes any combination of joining pieces together and restricting moves, I'm interested in the following questions:
- Do we know God's Number for other bandaged cubes?
- What bandaging would provide the highest possible God's Number? Is there some heuristic we can use to guess when one bandaging will be 'better' than another? Is there some information-theory limit on God's Number for a bandaged 3x3x3?
- Can we establish any kind of limit on the highest God's Number for other puzzles, such as Pyraminx, Skewb, 4x4x4, etc.?


----------



## riffz (Dec 6, 2010)

I'm just going to be a douche and ask for God's number when keychain solving.


----------



## cmhardw (Dec 6, 2010)

riffz said:


> I'm just going to be a douche and ask for God's number when keychain solving.


 
I'll add the restriction that every turn *must* be of a side which includes the corner that is attached to the keychain  (I think this number is perhaps still not known).


----------



## ben1996123 (Dec 6, 2010)

cmhardw said:


> I'll add the restriction that every turn *must* be of a side which includes the corner that is attached to the keychain  (I think this number is perhaps still not known).



Wouldn't solving with 1 corner always moving be the same as <ruf> solving?


----------



## Toad (Dec 6, 2010)

ben1996123 said:


> Wouldn't solving with 1 corner always moving be the same as <ruf> solving?


 
No. Think of the RUD corner and then do R U L F L' B etc... always moving.

EDIT: I get it now, silly me.


----------



## HaraldS (Dec 6, 2010)

I would also want to know gods number for other puzzles then just a normal 3x3x3. Whats Gods number for a super cube?


----------



## cuBerBruce (Dec 6, 2010)

cmhardw said:


> I'll add the restriction that every turn *must* be of a side which includes the corner that is attached to the keychain  (I think this number is perhaps still not known).



I note that the size of the "keychain group" is half the size of the whole cube group. So it would probably need a calculation effort of the same sort of scale that was used to prove God's number of 20 for the normal cube group. I get 25 as a simple lower bound. A 2-phase breadth-first search using on <Uw, Rw2, Fw2> as the subgroup could be done to get a decent upper bound.

I note that <Uw,Rw,Fw> is a subgroup of the fixed-corner cube group. The original post didn't make clear whether to allow subgroups of the fixed-corner cube group or fixed-edge cube group (or even the nothing-fixed cube group) as well as the center-fixed cube group.



ben1996123 said:


> Wouldn't solving with 1 corner always moving be the same as <ruf> solving?


 
Of course you mean <r,u,f> (or <Rw,Uw,Fw>) solving, not <ruf> solving. There is a huge difference. I remember a thread about this some years ago on the Yahoo group.


----------



## irontwig (Dec 6, 2010)

randomtoad said:


> No. Think of the RUD corner and then do R U L F L' B etc... always moving.


 
l b u b l' u


----------



## qqwref (Dec 6, 2010)

ben1996123 said:


> Wouldn't solving with 1 corner always moving be the same as <r,u,f> solving?


Yes, and <r,u,f> solving is a possible type of bandaging ("move this corner every turn" doesn't fit with my definition).

I'd be interested to know God's Number for the typical siamese cubes - <R,r,U>, <R,r,U,u>, <R,U,F>.

For anyone wondering about cuBerBruce's lower bound on <r,u,f>, there are 2.1626 * 10^19 positions, and the number of possible scrambles of n moves is f(n) = (3 * 2^(n-1))(3^n). Now f(24) gives fewer possible scrambles than they are positions (whereas f(25) is more), so we know that 24 moves cannot be sufficient to solve all positions.


----------



## vcuber13 (Dec 6, 2010)

what is the most amount of move needed to get it into the "normal" shape?
for example it is 8 for the cross


----------



## riffz (Dec 6, 2010)

cmhardw said:


> I'll add the restriction that every turn *must* be of a side which includes the corner that is attached to the keychain  (I think this number is perhaps still not known).


 
Lol, that's obviously what I meant.


----------



## Lucas Garron (Dec 7, 2010)

riffz said:


> Lol, that's obviously what I meant.


No, it's not.


----------



## riffz (Dec 7, 2010)

Lucas Garron said:


> No, it's not.


 
What else would I have meant?


----------



## Lucas Garron (Dec 7, 2010)

riffz said:


> What else would I have meant?


God's number for a keychain cube.
(Well, "while keychain solving.")


----------



## riffz (Dec 7, 2010)

Lucas Garron said:


> God's number for a keychain cube.
> (Well, "while keychain solving.")


 
...


----------



## qqwref (Dec 7, 2010)

Can anyone work out God's Number for the iCube? (Bandage every E-layer center or edge to the D-layer piece directly below it. You can choose whether to make D turnable.) I'll admit, I don't even know how many positions there are.

Would it be possible to write a type of God's Distribution calculator for arbitrary bandagings and/or move constraints? It wouldn't have to be fast.


----------



## jaap (Dec 7, 2010)

qqwref said:


> Can anyone work out God's Number for the iCube? (Bandage every E-layer center or edge to the D-layer piece directly below it. You can choose whether to make D turnable.) I'll admit, I don't even know how many positions there are.



I think there are 584,644,608 positions.
If you ignore the colours and only look at the shapes of the pieces, then there are 84584 configurations. I got this by computer search:


```
QTM    FTM-->
 v     0  1  2   3    4    5     6     7     8     9   10   11   12  13  14 Total
    0: 1  0  0   0    0    0     0     0     0     0    0    0    0   0   0     1
    1: 0  8  0   0    0    0     0     0     0     0    0    0    0   0   0     8
    2: 0  4 40   0    0    0     0     0     0     0    0    0    0   0   0    44
    3: 0  0 40 140    0    0     0     0     0     0    0    0    0   0   0   180
    4: 0  0 10 168  392    0     0     0     0     0    0    0    0   0   0   570
    5: 0  0  0  96  532  968     0     0     0     0    0    0    0   0   0  1596
    6: 0  0  0  16  372 1516  1808     0     0     0    0    0    0   0   0  3712
    7: 0  0  0   0  160 1196  3476  2304     0     0    0    0    0   0   0  7136
    8: 0  0  0   0   20  648  2976  5432  1828     0    0    0    0   0   0 10904
    9: 0  0  0   0    0  200  1588  5332  5416   996    0    0    0   0   0 13532
   10: 0  0  0   0    0   12   408  3056  6960  3588  372    0    0   0   0 14396
   11: 0  0  0   0    0    0     8   808  4392  6260 1664   72    0   0   0 13204
   12: 0  0  0   0    0    0     1    32  1080  4076 3652  712   48   0   0  9601
   13: 0  0  0   0    0    0     0     0    80   912 2604 1540  168   0   0  5304
   14: 0  0  0   0    0    0     0     0     0    80  712 1044  448  48   0  2332
   15: 0  0  0   0    0    0     0     0     0     0   72  408  424 160   0  1064
   16: 0  0  0   0    0    0     0     0     0     0    0   84  208 220  40   552
   17: 0  0  0   0    0    0     0     0     0     0    0    0   48 128  72   248
   18: 0  0  0   0    0    0     0     0     0     0    0    0    0  40  96   136
   19: 0  0  0   0    0    0     0     0     0     0    0    0    0   8  56    64
Total: 1 12 90 420 1476 4540 10265 16964 19756 15912 9076 3860 1344 604 264 84584
```

Multiplying that by 4! bandaged corner perms, and 4!*4!/2 unbandaged corner/edge perms gives the 584,644,608 positions I mentioned earlier. All these permutations are possible despite the bandaging, because Sune and Niklas are achievable for example.

This number of positions is too large to calculate God's Algorithm for with my current program, since its tables are rather sparsely filled.


----------



## qqwref (Dec 10, 2010)

Very nice work. But assuming you were only looking at the location of the bandaged bits in your shape calculations, shouldn't there be 4!*(4!*4!/2*2^3*3^3) = 1492992 permutations per shape, for a total of about 128 billion positions?

It's interesting that the shape alone can require as many as 14 FTM. I suppose an unstickered iCube could be a bit of a challenge itself, then. And this is pretty high - I wonder what the highest value would be for a 3x3 bandaging?

PS: Do you have to write a new program to compute God's Distribution for something like this, or do you have a more general one which just can start working when you give it the type of bandaging? If it's the latter, could you please release the program?


----------



## cuBerBruce (Dec 10, 2010)

I've been working on taking some of my code and creating a program to calculate distance distributions for arbitrary bandaging. It uses a hash table, which limits the number of positions it can handle to around 100 million with a 2GB process space. For a bandaging arrangement with a larger number of positions, it will calculate a partial distribution until it fills up the hash table.

I've used the Bicube described on Jaap's web site as a test case, and I'm not getting the same numbers as Jaap. So I'm not confident it's working correctly yet. I'm wondering if Jaap could provide a maneuver to generate any or all of the positions his program claims are 29f* positions, as my program seems to indicate none require more than 28 face turns. This should help in determining why my program is getting different results.

So far my program can do bandaging corners to edges and edges to centers (but not centers to the core). It doesn't support restricting moves at this time, although it supports either FTM or QTM.


----------



## qqwref (Dec 10, 2010)

Hm, you know, the code in a program that computes God's Number/Distribution for a bandaged cube has to be quite similar to the code in the optimal sliding-piece puzzle programs. I never programmed one of those, but I played around with sliding-piece puzzles a lot in the past (even inventing a handful of puzzles), and the idea is very very similar - it's just the topology that has changed.

And this topic reminds me that I have to finish the bandaged sim I've been thinking about since like 2007. Haha.


----------



## cuBerBruce (Dec 10, 2010)

qqwref said:


> Hm, you know, the code in a program that computes God's Number/Distribution for a bandaged cube has to be quite similar to the code in the optimal sliding-piece puzzle programs.


 
So you noticed my 15 puzzle result?

My bandaged cube program just simulates a plain 3x3x3 cube ( <U,D,L,R,F,B> ) and basically just checks that any move to be made doesn't violate any bandaging conditions.

EDIT:
I noticed that Jaap's Bicube page has a link to sequence A079771 in the OEIS. I notice that my numbers agree with that sequence rather than those on Jaap's page. I am thus presuming my numbers are correct after all.

For what it's worth, for the iCube with D layer turns allowed, I get:



Spoiler





```
C:\Bruce>RubikBandage.exe dfl drf dlb dbr db dr df dl
Bandaging 4 corners to edges and 4 edges to centers.
Using face turn metric.
distance   1: count =        15, total        16
distance   2: count =       126, total       142
distance   3: count =       714, total       856
distance   4: count =      3193, total      4049
distance   5: count =     13087, total     17136
distance   6: count =     49107, total     66243
distance   7: count =    173509, total    239752
distance   8: count =    599849, total    839601
distance   9: count =   2045011, total   2884612
distance  10: count =   6879520, total   9764132
distance  11: count =  22769894, total  32534026
Hash table full! (100000038)

C:\Bruce>RubikBandage.exe q dfl drf dlb dbr db dr df dl
Bandaging 4 corners to edges and 4 edges to centers.
Using quarter turn metric.
distance   1: count =        10, total        11
distance   2: count =        61, total        72
distance   3: count =       288, total       360
distance   4: count =      1106, total      1466
distance   5: count =      3860, total      5326
distance   6: count =     12518, total     17844
distance   7: count =     37928, total     55772
distance   8: count =    111853, total    167625
distance   9: count =    324470, total    492095
distance  10: count =    916049, total   1408144
distance  11: count =   2531932, total   3940076
distance  12: count =   6913825, total  10853901
distance  13: count =  18667168, total  29521069
distance  14: count =  49676931, total  79198000
Hash table full! (100000038)
```



Of course, the iCube has too many positions so my program can't generate the entire table.

I also note that the <R,U,F> group has been discussed on the Domain of the Cube forum ( http://cubezzz.duckdns.org/drupal/?q=node/view/198 ). It is known to have positions that require 26 quarter turns (when restricting moves to only those faces, of course).


----------



## qqwref (Dec 11, 2010)

cuBerBruce said:


> So you noticed my 15 puzzle result?


Nope, I was referring to more complex sliding-block solvers that support nontrivial puzzles, with larger blocks and L shapes and unmovable blocks and so on. I figure this is a similar concept to bandaging, just with different topology. I have a different solver that will also determine the deepest point of a given puzzle, if computationally possible. Some simple-looking puzzles require several hundred moves (defined as bringing any piece to any valid position) to get to the farthest position!



cuBerBruce said:


> My bandaged cube program just simulates a plain 3x3x3 cube ( <U,D,L,R,F,B> ) and basically just checks that any move to be made doesn't violate any bandaging conditions.


It's cool that it's so simple. I'm sure it is much more efficient at storing/tracking positions at each number of moves than anything I could write, though.



cuBerBruce said:


> For what it's worth, for the iCube with D layer turns allowed, I get:
> 
> 
> Spoiler
> ...


Interesting. Is it feasible to generate a couple thousand random positions and see how high the optimal HTM numbers get?



cuBerBruce said:


> I also note that the <R,U,F> group has been discussed on the Domain of the Cube forum ( http://cubezzz.homelinux.org/drupal/?q=node/view/198 ). It is known to have positions that require 26 quarter turns (when restricting moves to only those faces, of course).


Neat. I wonder how high the htm can go, though. I must say, I find qtm a little unnatural


----------



## jaap (Dec 11, 2010)

qqwref said:


> Very nice work. But assuming you were only looking at the location of the bandaged bits in your shape calculations, shouldn't there be 4!*(4!*4!/2*2^3*3^3) = 1492992 permutations per shape, for a total of about 128 billion positions?



You're quite right. I forgot about the orientations of the unbandaged pieces. In the back of my mind was the ordinary bandaged cube where there is no orientation independent of the shape.



qqwref said:


> PS: Do you have to write a new program to compute God's Distribution for something like this, or do you have a more general one which just can start working when you give it the type of bandaging? If it's the latter, could you please release the program?



I have a library of classes and functions that I can reuse, but I do have to write some additional code for determining what moves are allowed for each individual puzzle. It is not really in a releasable state.




cuberBruce said:


> I noticed that Jaap's Bicube page has a link to sequence A079771 in the OEIS. I notice that my numbers agree with that sequence rather than those on Jaap's page. I am thus presuming my numbers are correct after all.



Oh dear. I used to have just the htm list there, which is what the oeis took. I later replaced it with the htm vs qtm table done with a new program, and must have overlooked that the numbers had changed. I'll redo the table asap.

EDIT: I found my old program, fixed the bug, recomputed the table, updated the webpage. It was a subtle bug that didn't affect the configurations-only table at all.


----------



## cuBerBruce (Dec 11, 2010)

qqwref said:


> Nope, I was referring to more complex sliding-block solvers that support nontrivial puzzles, with larger blocks and L shapes and unmovable blocks and so on. I figure this is a similar concept to bandaging, just with different topology. I have a different solver that will also determine the deepest point of a given puzzle, if computationally possible. Some simple-looking puzzles require several hundred moves (defined as bringing any piece to any valid position) to get to the farthest position!



Yeah, I knew you were referring to more complex Klotski-style puzzles. I noticed someone just started a thread on Twisty Puzzles about Klotski, particularly about the "Sunshine" puzzle in the Klotski program. Of course, the 15 puzzle doesn't have any "bandaged" tiles.



qqwref said:


> It's cool that it's so simple. I'm sure it is much more efficient at storing/tracking positions at each number of moves than anything I could write, though.



Basically, at least 66 bits are needed to store a 3x3x3 position. For storage in the hash table, I convert the 3x3x3 positions into {ep,eo,cp,co} "coordinate" values, and then do some slight manipulation to store them into 4 unsigned short integers (2 bytes each) and an unsigned byte value. Another unsigned byte is used to store the distance value. I also use an array of 4-byte integers to store the hash table index of each new position, so I can efficiently walk through the positions of a given depth when looking for the positions at the next depth. So basically it uses 14 bytes per position.



qqwref said:


> Interesting. Is it feasible to generate a couple thousand random positions and see how high the optimal HTM numbers get?



It would have to be a rather different program. My program implements a breadth-first search. To optimally solve random positions, you probably want to do a depth-first search. There is also the issue of choosing (solvable) random positions. The neat thing about my BFS program is that it doesn't need to know in advance what positions are solvable. It simply requires that the set of solveable positions is a subset of the <U,D,L,R,F,B> group.



jaap said:


> EDIT: I found my old program, fixed the bug, recomputed the table, updated the webpage. It was a subtle bug that didn't affect the configurations-only table at all.


 
Jaap, I only get 5 35q* positions. Can you recheck your qtm numbers or provide me with the list of antipodes that you get?


Spoiler





```
C:\Bruce>RubikBandage.exe q lfu bur lub dfl drf dlb brd db bd df dl lu br
Bandaging 7 corners to edges and 6 edges to centers.
Using quarter turn metric.
distance   1: count =         6, total         7
distance   2: count =        17, total        24
distance   3: count =        31, total        55
distance   4: count =        60, total       115
distance   5: count =       106, total       221
distance   6: count =       161, total       382
distance   7: count =       274, total       656
distance   8: count =       469, total      1125
distance   9: count =       758, total      1883
distance  10: count =      1232, total      3115
distance  11: count =      2046, total      5161
distance  12: count =      3361, total      8522
distance  13: count =      5464, total     13986
distance  14: count =      8762, total     22748
distance  15: count =     14206, total     36954
distance  16: count =     22350, total     59304
distance  17: count =     34777, total     94081
distance  18: count =     52727, total    146808
distance  19: count =     76825, total    223633
distance  20: count =    104094, total    327727
distance  21: count =    131580, total    459307
distance  22: count =    147969, total    607276
distance  23: count =    148384, total    755660
distance  24: count =    128153, total    883813
distance  25: count =     95646, total    979459
distance  26: count =     61508, total   1040967
distance  27: count =     33900, total   1074867
distance  28: count =     18270, total   1093137
distance  29: count =      8308, total   1101445
distance  30: count =      4635, total   1106080
distance  31: count =      1873, total   1107953
distance  32: count =       620, total   1108573
distance  33: count =       211, total   1108784
distance  34: count =        11, total   1108795
distance  35: count =         5, total   1108800
distance  36: count =         0, total   1108800
```


----------



## jaap (Dec 11, 2010)

cuBerBruce said:


> Jaap, I only get 5 35q* positions. Can you recheck your qtm numbers or provide me with the list of antipodes that you get?


Gah! I was in too much of a hurry earlier this afternoon, and didn't realise the bug I found occurred twice in my code, once in a qtm routine as well. It should be fixed now and it matches your numbers. Thanks Bruce.

Edit: Here are the 5 qtm antipodes.
F1 R1 U1 F3 L3 U1 L2 F1 U2 R2 F3 R1 U2 F1 U3 R3 F2 L3 F1 R1 U2 L3 U2 R1 U2 L2 (26h*,35q*)

U2 L1 U3 F1 R1 F2 L3 F2 R1 U3 R2 F2 U1 L2 F1 L3 U2 R1 U1 F3 U1 L1 F1 R3 F2 L2 (26h*,35q*)

R1 U1 F3 U1 L1 F1 U1 L3 U1 R3 F3 U1 L1 F2 R1 F3 U3 R3 F3 U1 F3 L3 F1 U1 F1 U1 L3 U2 R1 U2 L2 (31h,35q*)
F3 U1 L1 F2 R1 U1 F3 L2 U1 R3 U2 L1 F1 R3 F2 L1 F2 R1 U1 F2 L3 F1 U1 L3 U2 R1 U2 L2 (28h*,37q)

U1 L1 F2 R3 F3 R1 U1 F2 L2 U3 L1 F2 R1 U1 F3 L3 U1 R3 U2 L1 F1 U1 F3 L3 U3 R1 U2 L2 (28h*,35q*)

R1 U1 F3 L1 F2 R3 F3 U3 R3 F1 R2 U1 R3 F1 L3 F2 R1 U2 L1 U3 F3 U3 F3 L1 F2 R3 F2 L2 (28h*,35q*)


----------



## cuBerBruce (Dec 13, 2010)

I've updated my program to allow specifying move restrictions (although it still only supports face turns). I've attached a zip file containing the executable and a text file describing how to use the program. Again, the program is for calculating distance distributions for bandaged cubes and move restrictions.

The program uses a large hash table, so it essentially requires 2GB of RAM in order to run efficiently. You quite likely might need more than that amount of RAM on the computer to run reasonably.


----------

