# God's algorithm calculations for the 4x4x4 "squares set"

I have computed God's algorithm for the set of Rubik's Revenge (4x4x4 cube) positions that are reachable by the following set of moves: { U^2, u^2, d^2, D^2, L^2, l^2, r^2, R^2, F^2, f^2, b^2, B^2 }. Actually, not all of the above moves need to be included in order to generate the whole set. Since these moves are expressed as squares of other basic moves in the group theory notation, the set of positions reachable by these moves is referred to as the Squares Group. In my analysis thus far, I have considered the four centers of a given face to be indistinguishable. That is, I am considering only the "plain" 4x4x4, not the 4x4x4 supercube (where all centers are taken to be distinguishable from the others). With this simplification, this set of positions does not actually form a mathematical group, so I will refer to it as the Squares Set here. 19 slice turns was found to be sufficient to solve any of the positions in this set.

I have also used two other metrics: "twist turns" and "block turns." Twist turns I consider to be moves involving movement along a single cut: { R^2, D^2, L^2, R^2, F^2, B^2, (U u)^2, (D d)^2, (L l)^2, (R r)^2, (F f)^2, (B b)^2 }. Block turns I consider to be any move that moves a 4x4x1 or 4x4x2 block with respect to the rest of the cube. This consists of the set of slice turns, the set of twist turns, plus { (u d')^2, (l r')^2, (f b')^2 }. (I include only half-turn moves for the various metrics in the present discussion, as I am here considering only moves that keep the puzzle within the Squares Set.)

The summary of the results is given below.

Squares Set of 4x4x4 cube, Slice turns distance positions reduced count unique wrt M 0 4 2 2 1 48 6 6 2 420 25 23 3 3,456 146 124 4 27,168 974 806 5 203,752 5,939 5,197 6 1,451,996 40,034 33,853 7 9,527,856 251,254 211,333 8 56,528,036 1,470,957 1,223,997 9 295,097,696 7,549,296 6,305,655 10 1,306,291,304 32,966,074 27,704,719 11 4,761,203,264 118,977,923 100,510,701 12 13,820,728,272 341,838,162 290,661,124 13 29,956,341,744 735,369,920 628,414,595 14 43,427,866,752 1,065,516,952 910,241,690 15 36,297,535,208 899,375,088 761,210,397 16 14,711,566,720 373,368,740 309,104,278 17 2,063,584,704 55,606,300 43,573,552 18 59,082,112 1,935,232 1,262,024 19 45,056 1,280 956 --------------- ------------- ------------- 146,767,085,568 3,634,274,304 3,080,465,032 Squares Set of 4x4x4 cube, Twist turns, Block turns Twist Turns Block Turns distance positions unique wrt M positions unique wrt M 0 4 2 4 2 1 36 5 72 11 2 252 15 864 50 3 1,728 70 9,700 403 4 11,528 374 101,060 3,267 5 72,300 1,988 939,956 25,028 6 431,188 10,423 7,748,796 182,815 7 2,459,832 55,600 56,687,544 1,252,926 8 13,361,660 291,127 362,251,572 7,775,843 9 68,407,980 1,464,351 1,975,717,680 41,920,351 10 326,021,992 6,914,502 8,792,371,296 185,298,651 11 1,414,642,236 29,844,904 28,896,905,328 606,099,406 12 5,361,506,980 112,742,406 56,844,273,080 1,190,199,719 13 16,520,565,624 346,616,171 43,883,159,504 921,188,861 14 36,467,453,404 764,073,198 5,918,564,320 125,844,537 15 47,828,766,672 1,002,434,703 28,351,768 672,920 16 30,852,487,408 648,178,826 3,024 242 17 7,546,175,832 159,746,983 0 0 18 362,229,856 8,020,105 0 0 19 2,450,544 67,417 0 0 20 38,512 1,862 0 0 --------------- ------------- --------------- ------------- 146,767,085,568 3,080,465,032 146,767,085,568 3,080,465,032

My program counted positions differing by the orientation of the whole cube as distinct positions, but only 180-degree whole cube rotations were considered. This results in four "solved" positions, the identity position where every facelet is on the "correct" face of the cube, and three positions obtained by rotating the identity position 180 degrees with respect to the three axes. Simply divide the numbers in the "positions" column by four to get the effective number of distinct positions when positions differing only by these whole cube rotations are considered to be the same.

My program used a sym-coordinate for the edge configuration of 21908 positions * 48 symmetries. So the number of "symmetry-reduced" positions was 21908*96*12^3 = 3634274304. Using two-bits per element, the main array was 908,568,576 bytes. Note, since the four centers of a given face are considered indistinguishable, the inverse of a position is ambiguous. Because of this, I believe you can't use antisymmetry to further reduce the positions.

The true number of positions when using symmetry with respect to all cubies, was found to be 3,080,465,032. I haven't performed a theoretical calculation to verify this number.