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

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

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

The corresponding upper estimate for a radius-15 ball is

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.

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

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

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.

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

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.

A different compression searches through a goal subgroup. Let

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

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.

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.