God's Number for a Bandaged 3x3x3

[cuBerBruce]

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]

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!

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.

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)

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

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

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]

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.

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.

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]

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.

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.

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.

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]

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]

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.