A worked replay and projected lower bound [frap-001B]
✍️source

    The fixed-frame model has a concrete replay on a three-layer puzzle. Work in the fixed-frame HTM convention of the complete cube account: a face quarter-turn, its inverse, or a half-turn costs one move, and words are read from left to right. Start at the solved state and apply the declared scramble

    \[w=R\ U\ R'\ U'\ F\ R\ U\ R'\ U'\ F'.\]

    The inverse word is

    \[w^{-1}=F\ U\ R\ U'\ R'\ F'\ U\ R\ U'\ R'.\]

    A sticker-level replay of the six fixed-frame face maps sends the solved state to the recorded scramble state and then returns to solved. The check represents each of the 54 pairs in how the cube models connect as a slot, applies the six quarter-turn permutations and their inverses, and enumerates the projected corner states breadth first through depth two. The token-by-token states and hashes are preserved in the replay receipt. Running the tracked replay checker with `node scripts/check-frap-b9b.js trees/frap-001B-replay.json` reproduces and compares the stored `replay_log`. The complete cube account supplies the move convention; the replay, hashes and 262-state count are the deterministic calculation reported here. The second replay is therefore a certificate for the move convention and the inverse, not merely an animation of a familiar sequence.

    1. What the small search certifies

      Project the scrambled state to its corner positions and orientations. Exhaustive projected search finds 262 distinct projected states at depths zero, one, and two, while the target is absent; a projected distance of three is therefore a lower bound for this state. The declared word has ten HTM moves, so the same replay gives the bounded report

      \[3\le d_{\rm HTM}(w,\mathrm {id})\le 10.\]

      The lower bound is admissible because projection forgets edge data and every full move projects to one projected move. The upper bound is a valid word because the inverse replay reaches the target. Neither bound claims that ten is shortest; a full optimality claim would need exhaustive search through depths four through nine or a matching certificate.

      2. Relation to layer-first and computer methods

        A player can recognize the displayed ten-move word as a repeated trigger pattern, but recognition is not a replacement for the state record. The complete layer-first method solves an arbitrary legal state by preserving completed layers and applying checked setup, trigger, and inverse-setup words; the computer account gives the corresponding upper-bound word and projected lower bound. This worked scramble shows how the two accounts meet: name the frame, replay the exact tokens, check the target, then state separately what has and has not been proved.

        The example is deliberately bounded. It demonstrates a complete scramble-and-replay loop and a concrete comparison of certificates; it does not claim to be a full optimal solve, a universal human algorithm, or a replacement for the all-state completeness argument.

        Backlinks

          Five encounters with a cube [frap-001C]

            Put a solved three-layer cube on a table and turn its right face once. The move is familiar, but it raises concrete puzzles: which labelled pieces moved, why can a visually plausible arrangement be impossible, and how can another person undo the turn without watching the first hand? Begin with these experiences, then introduce only the distinctions needed to explain them.

            One turn is larger than the visible face

              The shaded strip is only the visible part of the layer: the same stickers cross the front, right, back, top, and bottom faces; viewed from above, the top-face part is the corresponding rightmost strip. A whole-cube rotation would change the viewing frame, whereas this face move keeps the six centres fixed and changes one layer. The layered-cube family makes this distinction for every \(N\); the complete three-layer cube spells it out for the six outer generators.

              A sticker needs a home and a frame

                A player sees colours; a proof must also track each sticker's cubie and transported local frame. How the cube models connect follows one sticker through incidence position, cubie fibre, and fixed-frame coordinate. A colour quotient forgets labels, while a larger cube adds positions, so the state space changes with the question.

                A plausible state can still be impossible

                  Take a solved cube and twist one corner in place. Every sticker still has a cubie-sized home, and the three colours at that corner look locally consistent. But the corner orientations now have sum \(1\) modulo \(3\), whereas every face turn preserves sum \(0\). No sequence of legal turns can produce this state.

                  The complete three-layer cube derives the matching edge and permutation restrictions from the six generators. The calculation is useful at the table: it tells a solver when a scrambled-looking object was assembled illegally, and it tells a proof which state space is worth searching.

                  A human algorithm has to preserve these legal states while it borrows pieces from completed areas.

                  A formula often disturbs pieces that were already placed. The disturbance is acceptable only when the setup is undone and the completed pieces return. A working slot, a trigger, and an inverse setup make that promise visible. The complete layer-first method repeats this pattern through the cross, the first layer, the middle layer, and the last layer. Its completeness depends on the preservation and termination checks, not on the formula's familiarity.

                  Undoing a scramble checks the notation

                    The worked replay and projected lower bound fixes the viewing convention, records the ten tokens, and applies their inverse. Sticker replay returns to solved. A corner-only projected search finds no solution of depth at most two, so the evidence is the bounded statement

                    \[3\le d_{\rm HTM}\le 10.\]

                    The inverse word is an upper-bound witness; the projected search is a lower-bound witness. The computer account explains why these checks do not prove that ten is shortest. A state, a word, and a replay log are enough to test the notation before asking for a general solver.

                    Changing one ingredient changes the problem

                      Once the move, its frame, its local repair, and its replay are explicit, three variations separate the effects of enlarging the cube, changing the shape, and forgetting labels.

                      The layered-cube family develops the first variation; the incidence and facet construction in incidence, symmetry and moves develops the second; and which moves survive a quotient? gives the descent condition for the third. Framed orientations, label transport and topology, and scrambling, spectra and search then study the extra information each variation introduces or forgets. Their hypotheses stay attached to the concrete move that prompted the question.

                      A face turn can therefore be drawn, named, replayed, and checked before it is generalized. The resulting state maps and invariants support later formal certification or measured comparisons, while the examples here make clear which claim each later programme would have to establish.

                      From move sequences to play [frap-0006]

                        A formal move description becomes useful only when a player can apply it and reproduce its result. Play gives the mathematics an immediate test of intelligibility: a notation should identify a move unambiguously, a displayed turn should agree with the stated action, and replaying a sequence should reproduce the same state. Scrambling, undoing, recognizing a case, and following a solution all depend on those agreements.

                        A replay contract

                          Let \(S\) be a declared state space and let every legal move \(m\) be a reversible map \(S\to S\). A notation parser is correct only if it maps a token to one such map, with an inverse token satisfying

                          \[m^{-1}m=\operatorname {id}_S.\]

                          For a word \(w=m_1m_2\cdots m_k\), we read moves from left to right as in the complete layer-first method:

                          \[s_0=s,\qquad s_i=m_i(s_{i-1}),\qquad \operatorname {replay}(w,s)=s_k.\]

                          A replay test therefore records the initial state, the token list, the convention for viewing each face, and the final state. Replaying \(w\) followed by \(w^{-1}\) must return to \(s\); two displays are equivalent only after their resulting states, rather than their typography, agree.

                          Two traces that expose the conventions

                            The tetrahedron turn gives a short noncommuting trace. Starting at the recorded incidence position \((1,124)\), the \(H\)-move followed by the \(K\)-move reaches \((4,134)\). Reversing the order reaches \((3,234)\). The two words are therefore different maps, even though each move separately has order three. A player can check this by stepping through the two token lists and comparing the final records.

                            The cube face turn fixes the frame and turns only the chosen layer. The global shape map \(q(x,y,z)=(y,-x,z)\) sends the four \(z=1\) corners around a four-cycle; the local puzzle move restricts this map to that layer and fixes the opposite layer pointwise. This is a useful display test: a global rotation of the drawing is not the same operation as the local puzzle move, and the unturned center must not move merely because the picture was rotated.

                            From recognition to a solve

                              A reproducible solve has five recorded stages: identify the state in the chosen coordinates; state the target condition; choose a move word; replay it from the recorded state; and check the target and preserved invariants. The layer-first method supplies a human version: each stage fixes information and uses a stabilizer for what remains. The computer account supplies a search version: a returned word is an upper bound, while a projected-distance table gives a lower bound.

                              These certificates should be reported separately. A valid replay shows that the word reaches the target. A short word improves an upper bound in the named metric. A shortest-path claim additionally needs an exhaustive search or a matching lower bound. The distinction also applies to a scramble: scrambling and spectra requires the move law and length before a distributional claim can be evaluated.

                              The worked replay and projected lower bound makes this separation concrete: one fixed-frame scramble is replayed by its inverse, a projected search supplies a lower bound, and the ten-token word supplies an upper bound. The example closes the replay loop while leaving the all-state method and any optimality claim at their stated scopes.

                              What a playing interface can check

                                A small interface can make the contract visible without pretending to replace it. It can reject an unknown token, show the affected pieces, step through a word, undo by inverse tokens, and compare the final state with a target. It can also display parity, orientation, or subgroup coordinates as diagnostics, provided each coordinate is tied to the declared state model.

                                An animation illustrates a claim; the move map and replay log are the evidence for it. The interface should therefore expose the convention, the exact token sequence, and the before-and-after state so another person or program can reproduce the check. The existing Rubik's Cube resources collect notation, methods, and demonstrations; the companion FRAP repository can later host executable versions of these checks.

                                How the notes are organized [frap-000C]

                                  The developed mathematics follows one practical question: what data must a move carry so that we can later compose moves and test reachability? Incidence, symmetry and moves answers it in order. First, polytopes, flags and facet symmetry describe the shape and show their role in triangle and tetrahedron examples. Next, facet moves turn a local facet rotation into an action on incidence positions, with tetrahedron and cube calculations that make the construction concrete. Only then do positions, orientations and global constraints separate a piece's destination from transport in its local frame, while transfer and the effect of dimension connect that transport with a group homomorphism and compute the relevant local abelianizations.

                                  The cube examples above connect the general mathematics with solving and play. The later accounts use those concrete states and moves as their starting point:

                                  The transition between the abstract facet action and the fixed-frame cube coordinates is recorded in how the cube models connect. Read it before the all-\(N\) law if the distinction between incidence positions, cubie fibres and observations is new.

                                  1. General Rubik puzzles: the incidence actions, framed orientations and transfer developed below.
                                  2. The layered-cube family: piece types, layer turns and conventions as \(N\) varies.
                                  3. The layered-cube law: all-\(N\) state coordinates and a constructive characterization of reachability.
                                  4. The complete three-layer cube: explicit outer generators, impossible states, the standard count and a worked cleanup.
                                  5. Human methods and computer search: recognizable cases, algebraic effects, usability, move costs and optimality. The complete layer-first method supplies one full human construction, and computer solving and efficiency supplies exact small search, admissible bounds and subgroup reduction.
                                  6. From move sequences to play: notation, scrambling, recognition, replay and complete solves, including the worked replay and projected lower bound.

                                  Further connections relate the developed orientation and transfer calculations to label transport and topology and scrambling and search functions. The quotient-compatible move account gives the criterion for an identification of observations to inherit a puzzle action. Together these results compare transport, randomization and information loss around the same concrete move.

                                  Five encounters with a cube [frap-001C]

                                    Put a solved three-layer cube on a table and turn its right face once. The move is familiar, but it raises concrete puzzles: which labelled pieces moved, why can a visually plausible arrangement be impossible, and how can another person undo the turn without watching the first hand? Begin with these experiences, then introduce only the distinctions needed to explain them.

                                    One turn is larger than the visible face

                                      The shaded strip is only the visible part of the layer: the same stickers cross the front, right, back, top, and bottom faces; viewed from above, the top-face part is the corresponding rightmost strip. A whole-cube rotation would change the viewing frame, whereas this face move keeps the six centres fixed and changes one layer. The layered-cube family makes this distinction for every \(N\); the complete three-layer cube spells it out for the six outer generators.

                                      A sticker needs a home and a frame

                                        A player sees colours; a proof must also track each sticker's cubie and transported local frame. How the cube models connect follows one sticker through incidence position, cubie fibre, and fixed-frame coordinate. A colour quotient forgets labels, while a larger cube adds positions, so the state space changes with the question.

                                        A plausible state can still be impossible

                                          Take a solved cube and twist one corner in place. Every sticker still has a cubie-sized home, and the three colours at that corner look locally consistent. But the corner orientations now have sum \(1\) modulo \(3\), whereas every face turn preserves sum \(0\). No sequence of legal turns can produce this state.

                                          The complete three-layer cube derives the matching edge and permutation restrictions from the six generators. The calculation is useful at the table: it tells a solver when a scrambled-looking object was assembled illegally, and it tells a proof which state space is worth searching.

                                          A human algorithm has to preserve these legal states while it borrows pieces from completed areas.

                                          A formula often disturbs pieces that were already placed. The disturbance is acceptable only when the setup is undone and the completed pieces return. A working slot, a trigger, and an inverse setup make that promise visible. The complete layer-first method repeats this pattern through the cross, the first layer, the middle layer, and the last layer. Its completeness depends on the preservation and termination checks, not on the formula's familiarity.

                                          Undoing a scramble checks the notation

                                            The worked replay and projected lower bound fixes the viewing convention, records the ten tokens, and applies their inverse. Sticker replay returns to solved. A corner-only projected search finds no solution of depth at most two, so the evidence is the bounded statement

                                            \[3\le d_{\rm HTM}\le 10.\]

                                            The inverse word is an upper-bound witness; the projected search is a lower-bound witness. The computer account explains why these checks do not prove that ten is shortest. A state, a word, and a replay log are enough to test the notation before asking for a general solver.

                                            Changing one ingredient changes the problem

                                              Once the move, its frame, its local repair, and its replay are explicit, three variations separate the effects of enlarging the cube, changing the shape, and forgetting labels.

                                              The layered-cube family develops the first variation; the incidence and facet construction in incidence, symmetry and moves develops the second; and which moves survive a quotient? gives the descent condition for the third. Framed orientations, label transport and topology, and scrambling, spectra and search then study the extra information each variation introduces or forgets. Their hypotheses stay attached to the concrete move that prompted the question.

                                              A face turn can therefore be drawn, named, replayed, and checked before it is generalized. The resulting state maps and invariants support later formal certification or measured comparisons, while the examples here make clear which claim each later programme would have to establish.

                                              Related

                                                A complete layer-first method [frap-0017]

                                                  The three-layer model in the complete cube account turns a human solve into a sequence of stabilizer problems. We keep the fixed frame and write \(U,D,F,B,R,L\) for clockwise quarter-turns as seen from the named face. A prime is an inverse and a superscript \(2\) is a half-turn; a word is read from left to right. The bottom face \(D\) is the first layer, so its center fixes the target colour and the four side centres fix the cross alignment. The notation and face-view convention agree with the cube notation notes.

                                                  Effects, setup, and preservation

                                                    A slot is a destination for one corner or edge. A setup word \(s\) brings a chosen case to the working slot; a trigger \(t\) performs the local change there; and \(s t s^{-1}\) transports that change to another location. This is conjugation in the move group, not a promise that the transported word has the same visible support before the replay is checked. A commutator

                                                    \[ [a,b]=a b a^{-1}b^{-1} \]

                                                    is useful when \(a\) and \(b\) overlap in a controlled way. Its support must still be computed in the current convention: cancellation in the group word does not by itself prove that every other piece is fixed.

                                                    Let \(H_i\) be the subgroup fixing everything completed before stage \(i\). A stage is valid when each of its words lies in \(H_i\) after the setup data have been restored. Thus a solve follows a descending chain

                                                    \[G\supseteq H_{\rm cross}\supseteq H_{\rm first}\supseteq H_{\rm middle}\supseteq H_{\rm last\,orientation}.\]

                                                    The inclusions describe preservation, while the case table below gives the progress that makes the chain terminate. This separates the algebraic question “what does the word change?” from the practical questions of recognition, memory, and execution.

                                                    The complete seven-stage method

                                                      The following method is complete under the stated case conventions. At every stage, rotate only the working view or use a setup word; never rotate the whole cube while a positional convention is being recorded. A displayed algorithm is a witness for its local effect. Its inverse and a conjugate supply the other orientations and slots.

                                                      1. Cross. Solve the four \(D\)-edges one at a time, matching each side colour to its centre. If a target edge is in the top layer, bring it above its slot and insert it with \(F^2\) or a quarter-turn setup. If it is in the first layer with the wrong orientation, eject it to the top and insert it again. Earlier cross edges are kept out of the working slot.
                                                      2. First-layer corners. Put a target corner above its \(D\) slot at \(UFR\). Repeat \(T=R' D' R D\) until the target sticker faces down and the two side stickers match. The word \(T\) fixes the already solved cross after the setup is restored; at most four repetitions are needed. A corner incorrectly occupying the slot is first ejected with the same trigger, then treated as a top-layer case.
                                                      3. Middle edges. With the solved layer on the bottom, align a top-layer edge with its side centre. To insert it on the right use
                                                        4. \[I_R=U R U' R' U' F' U F,\]

                                                        and to insert it on the left use

                                                        \[I_L=U' L' U L U F U' F'.\]

                                                        Both words restore the first layer. If a middle edge is misplaced, use either insertion to eject it, then solve the resulting top-layer case.

                                                      4. Last-layer cross. Ignore the side colours and orient the four \(U\)-edges with
                                                        5. \[X=F R U R' U' F'.\]

                                                        With the \(U\)-face viewed from above, a line is held horizontal and an L is held at the back-left. The same word changes the zero-, two-, or four-oriented-edge cases to a case with strictly more oriented edges after the indicated setup; repeat until the cross is present.

                                                      5. Last-layer edges. First restore the side colours of the four cross edges. The checked three-edge cycle
                                                        6. \[P=R U' R U R U R U' R' U' R^2\]

                                                        fixes the corners and cycles three \(U\)-edges. Together with a \(U\)-turn, its conjugates generate all permutations of the four cross edges: a 4-cycle and a 3-cycle generate \(S_4\). Apply a setup, one or more copies of \(P\) or \(P^{-1}\), and undo the setup.

                                                      6. Last-layer corners. Put a correctly located corner at \(UFR\); if none is located, apply the word once and inspect again. The corner cycle
                                                        7. \[C=R' F R' B^2 R F' R' B^2 R^2\]

                                                        fixes the cross edges and cycles the three other \(U\)-corners. Its conjugates and \(U\)-turns generate \(S_4\), so repeated applications place all four corners without changing their orientations.

                                                      7. Last-layer corner orientation. Keep the cube fixed. At \(UFR\), repeat \(T=R'D'RD\) until that corner is oriented; turn only \(U\) to bring the next unsolved corner to \(UFR\), and repeat. During this stage the visible lower layers look disturbed, but after the last corner the accumulated orientation sum is zero and every earlier piece returns to its solved position.

                                                      The method uses only a small vocabulary of triggers. The setup words are the memory burden; each trigger has a recognizable local effect. The two places where an algorithm appears to disrupt completed material (the corner orientation stage and an ejection of a misplaced piece) are deliberate: the word is applied until the current local case is solved, after which the preservation invariant is restored.

                                                      Why the cases terminate

                                                        We now justify completeness rather than infer it from successful demonstrations. A cross edge can always be moved to the top layer or ejected from its slot, and a quarter-turn or half-turn inserts it into a matching slot. Removing one solved edge leaves a connected set of unsolved slots, so four repetitions finish the cross. The corner trigger has a nonzero twist effect at \(UFR\) and fixes the cross after each full insertion; the eject-and-reinsert rule therefore solves four corners. The two middle insertions are inverses after reflection of the working view, and the same ejection argument solves four middle edges.

                                                        For the last layer, the edge-orientation word \(X\) changes the orientation pattern in the standard line/L/point cases while fixing both completed layers. The finite list of patterns has representatives point, line, and L; the prescribed setup makes the number of oriented edges increase, so the process reaches the cross. After orientation, \(P\) is a 3-cycle on edges and \(U\) is a 4-cycle. These generate \(S_4\), proving that the edge-position stage reaches every permutation. The analogous checked effect of \(C\), together with \(U\), gives \(S_4\) on corners.

                                                        Finally, \(T\) changes the orientation of the working corner while the temporary permutation cancels after the corner is finished and the next corner is brought into place. The corner orientation sum from the cube constraints is zero, so the final corner is forced when the other three have been oriented. Thus every state satisfying the three reachability tests has a finite word supplied by these stages. This is a completeness proof for the method, not an optimality claim.

                                                        One annotated local solve

                                                          Suppose the first two layers are solved, the \(U\)-cross is oriented, and the three-edge cycle needed to place the \(U\)-edge at the back is visible. Hold that edge at the slot to be fixed and apply \(P\); if the cycle runs the other way, apply \(P^{-1}\). The corners and all lower pieces return to their previous states. If the desired edge is not in the working support, choose a setup \(s\) that brings it there and replay

                                                          \[s P s^{-1}.\]

                                                          After the edge positions are correct, use the same inspect--setup--cycle pattern for \(C\). Only then use \(T\) at \(UFR\), counting quarter-turns until the corner's \(U\)-sticker points up. The visible disorder during this last replay is expected; the final inverse setup and the orientation sum certify that the solved state has returned. This is the smallest complete trace of the method: recognize a case, transport a checked effect, and finish inside the next stabilizer.

                                                          A block-building or Roux-style organization can reduce the number of stages for an experienced solver, but it changes the recognition and preservation cases. It should be compared through the same questions—what is fixed, what subgroup remains, which effects are checked, and what is remembered—rather than by treating a lower move count as a complete measure of usability. The cube resource notes collect contrasting organizations for that later comparison.

                                                          Computer solving and efficiency [frap-0018]

                                                            A computer solver answers a sharper question than a human method: from a recorded state, what is the shortest path to solved, or what short path can be found quickly? The answer depends on the move metric, the state coordinates, and the information retained by the search. We use the fixed-frame ordinary 3-layer action from the complete cube account, with the six outer face turns as generators. The methods chapter supplies the group-action graph viewpoints; here they become finite search procedures.

                                                            Move graphs and lower bounds

                                                              For a move metric \(M\), let \(\Gamma _M\) be the undirected graph whose vertices are legal cube states and whose edges apply one allowed move, with each edge weighted by that move's cost in \(M\). A graph distance is the function

                                                              \[d_M(x,y)=\text {the minimum total edge weight on a path from }x\text { to }y.\]

                                                              The metric diameter is the maximum of \(d_M(x,y)\) over legal states; in a transitive move graph it is also the maximum distance from the solved state. For unit-cost moves, breadth-first search from solved labels every reachable vertex by exact distance, because the first time a vertex is reached there is no shorter path left in the earlier layers. With non-unit weights, Dijkstra's algorithm supplies the analogous exact labels. A depth-first method can use the same graph without storing all of it; optimal branch-and-bound and IDA* need a certified lower bound to prune safely.

                                                              The usual half-turn metric (HTM) charges each face quarter-turn, inverse quarter-turn, or half-turn one move. The quarter-turn metric (QTM) charges a half-turn two moves. A word can therefore be shorter in HTM while representing the same group element; an efficiency claim is incomplete until its metric and move set are named.

                                                              A simple counting bound already separates search from proof. In HTM there are at most eighteen first moves and at most seventeen choices after the first if an immediate inverse is suppressed. Hence a ball of radius \(r\) has at most

                                                              \[1+18\sum _{i=0}^{r-1}17^i\]

                                                              vertices. The reachable 3-layer state count from the complete cube account is

                                                              \[N_3=8!\,12!\,3^7\,2^{10} =43\,252\,003\,274\,489\,856\,000.\]

                                                              The corresponding upper estimate for a radius-15 ball is

                                                              \[1+18\sum _{i=0}^{14}17^i =3\,220\,225\,932\,948\,542\,767<N_3.\]

                                                              Thus not every state can lie within fifteen moves, so the HTM diameter is at least \(16\). This is only a counting lower bound: it does not exhibit a state at distance sixteen, and it says nothing about a particular scramble.

                                                              One exact small search

                                                                The same procedure can be made exhaustive on the corner-only cube. In a fixed-frame labelling (there are no centers on a \(2\times 2\times 2\)), a legal state is a corner permutation together with seven independent twists, so there are

                                                                \[8!\,3^7=88\,179\,840\]

                                                                labelled states. Quotienting by the twenty-four orientations of the whole cube leaves \(3\,674\,160\) rotation classes. Enumerate the six face quarter-turns, their inverses, and the six face half-turns; canonicalize each state by the whole-cube rotation action, and keep the first depth at which each rotation class is seen. The resulting layer sizes in HTM are

                                                                \[1,9,54,321,1847,9992,50136,227536, 870072,1887748,623800,2644.\]

                                                                They sum to \(3\,674\,160\); the last nonempty layer is \(11\). Thus this finite breadth-first computation proves that the rotation-quotient corner-only cube has diameter eleven in HTM. It is an exact search: every rotation class is covered and every recorded depth is a shortest distance. The calculation agrees with the published exhaustive layer table for the pocket cube, p. 3. The calculation also illustrates why the full 3-layer graph is not attacked by naïve BFS: its state count is larger by many orders of magnitude.

                                                                Admissible heuristics and pattern databases

                                                                  A projection heuristic forgets part of a state. If \(\pi \) maps the full move graph to a smaller graph and every full move projects to a projected path of no greater total cost, then

                                                                  \[h_\pi (x)=d_{\pi }(\pi (x),\pi (\mathrm {id}))\]

                                                                  never overestimates the full distance: projecting a full solution gives a projected solution of no greater cost. For example, a table entry \(h_\pi (x)=2\) certifies that every full solution from \(x\) costs at least two. Such a function is an admissible heuristic. A maximum of admissible heuristics is admissible; a sum needs an additional cost-partition argument and is not automatically safe. The graph maps here are specified by these equations and move lists, so a separate vector diagram would add no state or cost data.

                                                                  A pattern database stores these projected distances in a table indexed by a selected set of cubies or coordinates. Reverse breadth-first search fills the table once; an iterative-deepening A* (IDA*) search then explores depth thresholds while pruning a node \(x\) whenever \(g+h_\pi (x)\) exceeds the threshold. Korf's Rubik's-cube computation used this combination of pattern databases and IDA* for optimal solutions to random instances the AAAI paper, abstract and sections “Problem Space” and “Pattern Databases”. The table certifies a lower bound, while the exhaustive threshold search is what certifies optimality.

                                                                  For the 3-layer coordinates, a corner-orientation table has \(3^7\) entries, an edge-orientation table has \(2^{11}\), and a chosen edge-position table can be indexed separately. Taking the maximum of their exact projected distances is safe and often much stronger than either table alone. Memory, lookup cost, and the number of expanded nodes are measurable resources; none of them changes the definition of the shortest distance.

                                                                  Subgroup reduction and two phases

                                                                    A different compression searches through a goal subgroup. Let

                                                                    \[G_1=\langle U,D,R^2,L^2,F^2,B^2\rangle .\]

                                                                    In this subgroup the corner and edge orientations are fixed, and the four middle-slice edges stay in their slice. A first phase searches the full generator set for a word taking the scramble into \(G_1\); a second phase solves inside \(G_1\) using only its generators. The phase-1 coordinates are corner orientation, edge orientation, and the choice of the four slice edges, with raw size

                                                                    \[3^7\,2^{11}\binom {12}{4}=2\,217\,093\,120.\]

                                                                    Pruning tables and symmetry reductions store only useful projections of this space.

                                                                    Kociemba's two-phase account describes IDA* over these coordinates and explicitly distinguishes a fast near-optimal solver from an optimal solver the Phase 1, Phase 2 and optimality paragraphs. A solution found by one phase-1 word followed by a phase-2 word is a valid upper bound. It becomes a proof of optimality only when every shorter possibility under the declared metric has been excluded. Restricting phase two to \(G_1\) makes the search practical, but can omit an overall shortest route that leaves and later re-enters \(G_1\).

                                                                    This reduction is the computer analogue of the preservation chain in the complete layer-first method: both deliberately fix information before solving what remains. The difference is the certificate. A human stage records a finite case argument; a search stage records a lower bound, an upper-bound word, and the unexplored threshold.

                                                                    Efficiency and growing cubes

                                                                      A useful report separates four measurements: solution length in a named metric, number of expanded nodes, peak table memory, and wall-clock time on named hardware. Recognition and move execution belong to the human method; node expansions and table construction belong to the computer method. A shorter returned word is evidence of a better upper bound, not by itself a proof that the word is shortest.

                                                                      For the growing \(N\times N\times N\) family, the asymptotic question is how the diameter changes with \(N\) when a move rotates one legal slice. Demaine, Demaine, Eisenstat, Lubiw and Winslow prove a scoped result for this family: the diameter is \(\Theta (N^2/\log N)\), with a counting lower bound and a parallelized upper-bound construction their abstract and Section 2, “Common Definitions”. Their model allows a legal slice rotation as defined there; that move convention must be checked before transferring the statement to a different layered-cube convention.

                                                                      The fixed-frame 3-layer count and the exact corner-only search give two finite anchors for that asymptotic discussion. The asymptotic theorem does not make a particular 3-layer word optimal, and the exact small search does not predict the table size or diameter of larger cubes. Across all sizes, correctness means reaching the target; optimality means proving a shortest path; efficiency means reporting the resources used to obtain either one.

                                                                      Computer solving therefore extends the earlier construction in three controlled directions: exact graph distances on a small quotient, admissible lower bounds for the full state space, and subgroup reductions that trade completeness of the search for speed. These distinctions let a later return to play report a solver's output without confusing a valid solve, a short solve, and a certified optimum.

                                                                      This chapter is a mathematical specification, not a Lean-certified solver. For comparison, rubik-lean4 at commit b8a5a09 formalizes the fixed-frame move and sticker correspondence, while rubiks-cube-group at commit 3baebd73 formalizes the legal-state subgroup; neither repository is used here as a formal proof of the search, diameter, or optimality claims above.

                                                                      How the cube models connect [frap-001A]

                                                                        An abstract cube turn records incidence positions and restricts a shape symmetry to one facet. A layered-cube turn records cubies, stickers, frames and allowed layers. For the ordinary three-layer cube these are two descriptions of the same action; the map below identifies their coordinates.

                                                                        From facet incidence to the 54-sticker state

                                                                          The facet calculation in one ordinary cube face turn selects the facet-colored part of the incidence set. Put the cube's surface cells at \(p\in \{-1,0,1\}^3\ \text {with}\ \lVert p\rVert _\infty =1\). A visible sticker is a pair \((p,n)\), where \(n=\operatorname {sgn}(p_i)e_i\) for each nonzero coordinate \(p_i\). Thus a corner has three visible normals, an edge has two, and a face center has one:

                                                                          \[8\cdot 3+12\cdot 2+6=54.\]

                                                                          The vertex--facet incidences in the facet-colored set map to the pairs above by sending a cube vertex, edge, or facet to its surface-cell coordinate and its incident facet normal. Conversely, the zero-coordinate pattern of \(p\) determines the cubie (three nonzero entries for a corner, two for an edge, one for a centre), and \(n\) determines the incident facet, so this is a bijection between the 54 incidences and the 54 pairs. The cubie counts and this incidence decomposition follow the general model in [bonzio2018nxnxn, Sections 2--3]; the displayed pairing and 54-count are the calculation used here. For \(N=3\), group these pairs into eight corner and twelve edge sticker fibres, leaving the six center positions as fixed frame marks. A legal outer-face move preserves this partition and carries the labels in a corner fibre or edge fibre to the corresponding destination fibre. Write \(C_p=\{(p,\operatorname {sgn}(p_i)e_i):p_i\ne 0\}\) for a corner fibre and \(E_p\) for an edge fibre. For a corner, order its normals as \(L_p=(u_p,f_p,r_p)\), where \(u_p=\operatorname {sgn}(p_3)e_3\), \(f_p=\operatorname {sgn}(p_2)e_2\), and \(r_p=\operatorname {sgn}(p_1)e_1\). For an edge, put first the U/D normal when \(p_3\ne 0\), otherwise the F/B normal, and put the other normal second. A move sends \(C_p\) or \(E_p\) to a destination fibre. Let \(k_p\in \{0,1,2\}\) be the index of the transported U/D normal in \(L_{p'}\). If the source cubie has \(p_3=+1\), set \(x_p=k_p\); if it has \(p_3=-1\), set \(x_p=-k_p\) in \(\mathbb Z_3\). Thus each side turn gives two \(+1\) and two \(-1\) corner twists, while U/D turns give zero, matching the U/D-sticker convention in the complete three-layer cube. For an edge, its distinguished normal agrees or disagrees with the first destination label, giving \(z\in \mathbb Z_2\). This explicit extraction fixes each per-fibre bijection and the destination permutation without asserting an unstated cyclic convention. Therefore it induces exactly the fixed-frame coordinates

                                                                          \[(\sigma ,x;\tau ,z)\in S_8\times (\mathbb Z_3)^8 \times S_{12}\times (\mathbb Z_2)^{12}\]

                                                                          used in the complete three-layer cube. More explicitly, if a move sends a corner fibre \(C_p\) to \(C_{p'}\), set \(\sigma (p)=p'\); the destination edge fibre similarly gives \(\tau \). For the positive-\(z\) turn \(q(x,y,z)=(y,-x,z)\) from one ordinary cube face turn,

                                                                          \[((1,1,1),e_z)\longmapsto ((1,-1,1),e_z),\qquad ((1,1,1),e_y)\longmapsto ((1,-1,1),e_x).\]

                                                                          This exhibits both the destination corner and the transported local frame. The induced map is a change of state description for the legal action: it sends a sticker permutation to its corner and edge destination permutations together with the local frame changes. It does not assert that every permutation of the 54 positions is a legal cube move.

                                                                          This also separates two kinds of forgetting. Passing from the incidence action to the displayed coordinates forgets the individual sticker addresses inside each recorded local frame. Passing from labelled cubies to an ordinary colour observation forgets equal-looking labels. The latter is the observation quotient discussed in which moves survive a quotient, and it is a separate identification of states rather than a change in these coordinates.

                                                                          What changes when layers are added

                                                                            For larger \(N\), the same surface-cell description retains the corner and edge fibers but adds coupled-edge and center orbits. Inner layers move those new fibers, and even and odd sizes have different orbit signatures. The all-\(N\) coordinates in the layered-cube law therefore extend the three-layer state description rather than replace it. Their parity and orientation equations are stated for a labelled fixed-frame model; they are not obtained by treating every center sticker as one of the twelve ordinary edges.

                                                                            The transition is consequently a specialization in one direction: the \(N=3\) outer-layer case of the family of layered cubes gives the ordinary fixed-frame action, while the abstract facet action explains why that outer turn moves precisely the selected surface fibers. Whole-cube rotations, marked centers, central slices and colour-only identifications are additional choices, not silent changes of coordinates.

                                                                            What the identification supports

                                                                              The explicit identification supports this chain of state descriptions:

                                                                              1. incidence, flags and a local facet action explain what a move is;
                                                                              2. the layered model and its first law explain which fibres and constraints appear as \(N\) changes;
                                                                              3. the fixed-frame three-layer coordinates make the three familiar constraints and their constructive sufficiency explicit;
                                                                              4. human methods and computer searches use the same state action while assigning different meanings to preservation, cost and optimality;
                                                                              5. a declared move word can be replayed and checked against these state descriptions.

                                                                              Three linked comparisons use the same distinctions. Label transport and branched unfolding study return maps on simplex labels; compatible quotients test whether an identification of sticker observations inherits a move; and scrambling and spectra study which functions retain memory under a declared move law. These are comparisons of transport, forgetting and randomization, not identifications with the fixed-frame cube action.

                                                                              The complete three-layer cube [frap-0016]

                                                                                The all-size law has two reasons to be followed by a separate three-layer account. A \(3\times 3\times 3\) cube has no moving centers or coupled edges, and its familiar three tests can be checked directly on the six outer-face generators. We use a fixed frame and unmarked centers. A labelled state is therefore

                                                                                \[(\sigma ,x;\tau ,z)\in S_8\times (\mathbb Z_3)^8 \times S_{12}\times (\mathbb Z_2)^{12}.\]

                                                                                Here \(\sigma \) and \(\tau \) record corner and edge positions. The corner frame uses the U/D sticker to record a twist in \(\mathbb Z_3\); an edge frame uses the U/D or F/B sticker convention to record a flip in \(\mathbb Z_2\). The six centers fix the frame but have no recorded orientation. This is the ordinary cube model, rather than a supercube model with marked centers.

                                                                                Generators and the three obstructions

                                                                                  Write \(R,L,U,D,F,B\) for clockwise quarter-turns as seen from the corresponding face; inverses and squares are allowed. Each turn is a four-cycle on corners and a four-cycle on edges. Thus it changes both permutation signs, leaving

                                                                                  \[\operatorname {sgn}(\sigma )=\operatorname {sgn}(\tau )\]

                                                                                  unchanged. A turn of U or D changes no corner twist in this convention; a turn of another face adds one and subtracts one at opposite corners. The four affected edge frames change in pairs. Consequently every reachable state satisfies

                                                                                  \[\sum _{i=1}^{8}x_i=0\pmod 3,\qquad \sum _{j=1}^{12}z_j=0\pmod 2.\]

                                                                                  These checks are generator checks, so they also cover inverses, powers and arbitrary words. They give immediate impossible states: one twisted corner has corner sum \(1\); one flipped edge has edge sum \(1\); and a swap of two corners alone has odd corner sign but even edge sign. A state can pass all three tests and still require a construction; necessity is not sufficiency. The coordinate convention and invariant calculation agree with the 3-layer case of [salkinder2021nxnxn, Theorems 8--18].

                                                                                  Localized effects and sufficiency

                                                                                    We now describe a constructive cleanup. Let \([a,b]=aba^{-1}b^{-1}\) and \([a:b]=aba^{-1}\). The word

                                                                                    \[c=[[R:U],D]\]

                                                                                    is a three-cycle on corners and fixes the other corner positions. A direct coordinate replay gives this cycle; conjugating by face turns moves it through the connected corner orbit. Hence these conjugates generate \(A_8\). For edges, the outer-turn word

                                                                                    \[e=R\,U^{-1}\,R\,U\,R\,U\,R\,U^{-1}\,R^{-1}\,U^{-1}\,R^2\]

                                                                                    is a three-cycle on three edges and fixes the corners (the familiar U-permutation). Conjugates generate \(A_{12}\). The displayed words are useful witnesses, not a claim that they are short in every metric.

                                                                                    Given a state satisfying the sign equation, apply one face turn when the common sign is odd. The remaining corner and edge permutations are even. Use the conjugated corner cycles to clear \(\sigma \), then the conjugated edge cycles to clear \(\tau \); each cleanup is chosen in the subgroup that fixes the already-cleared piece type. The sign equation is exactly what makes both cleanups possible.

                                                                                    After positions are restored, the orientation kernels are generated by local commutators. The standard corner trigger \((R^{-1}D^{-1}RD)^2\) restores positions while twisting two corners in opposite directions; setup, trigger, and inverse setup transport this effect to any pair. For edges, the local trigger \(F R U R^{-1}U^{-1}F^{-1}\) is combined with its conjugate and inverse setup to give a pure two-edge flip. A direct sticker replay checks that support and the two flipped signs. Their transported effects generate the kernels

                                                                                    \[\ker ((\mathbb Z_3)^8\to \mathbb Z_3)\quad \text {and}\quad \ker ((\mathbb Z_2)^{12}\to \mathbb Z_2).\]

                                                                                    The two displayed sums are therefore the only orientation obstructions. Reversing the cleanup word reaches every tuple satisfying the three tests. This is a constructive subgroup argument; it does not identify a shortest solution.

                                                                                    Count and a worked reachability check

                                                                                      There are \(8!\) corner permutations, \(12!\) edge permutations, \(3^8\) raw corner orientations and \(2^{12}\) raw edge orientations. The sign equation removes a factor of two, and the two orientation sums remove factors of three and two. Thus the number of labelled reachable states is

                                                                                      \[8!\,12!\,3^7\,2^{10} =43\,252\,003\,274\,489\,856\,000.\]

                                                                                      For a concrete reachability check, start from solved and apply the corner cycle \(c\). Its corner permutation is a 3-cycle, its edge permutation is the identity, and its orientation sums remain zero, so it passes every test. Applying \(c^{-1}\) returns to solved. More generally, the cleanup above factors any passing state into a sign correction, even corner and edge permutations, and orientation-pair operations; this gives an explicit solve word once the required cycles and setup positions have been selected.

                                                                                      Unmarked centers explain why a whole-cube rotation is not counted as a generator and why the center colors fix a frame rather than add twelve more coordinates. The all-\(N\) chapter keeps these choices visible when moving centers and coupled edges return. The next chapters can now discuss human methods and computer search using this completely specified 3-layer action.