God's Number for a Bandaged 3x3x3

qqwref

qqwref

Legend
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA ID
2006GOTT01
YouTube
Visit Channel
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.?
 
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 :p (I think this number is perhaps still not known).
Click to expand...

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?
Click to expand...

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.
 
Last edited:
ben1996123 said:
Wouldn't solving with 1 corner always moving be the same as <r,u,f> solving?
Click to expand...
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.
 
Last edited:
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.
 
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.
Click to expand...

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:

Code: 
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.
 
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?
 
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.
 
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.
 
You must log in or register to reply here.

Similar threads

B
God's number for the FTO
Replies
10
Views
812
BadDisplayName
B
iguana
What is God's number for a 3-gen scramble?
Replies
8
Views
646
Bruce MacKenzie
Bruce MacKenzie
A
4x4x4 OBTM (WTM) upper bound improved from 55 to 54
Replies
1
Views
441
SpeedCubingLord
SpeedCubingLord
D
God's Number and Pieces Rubik's Cube
Replies
5
Views
648
Deleted member 27249
D
C
Man's number challenge
Replies
6
Views
1,043
CubingKid
C
Back
Top