Vertices and edgesThe cube group is a Cayley graph. Each of the 43,252,003,274,489,856,000 positions of a 3×3 is a vertex, and the 18 face turns (U U2 U' and so on for six faces) are its edges. The graph is 18-regular and looks the same from every vertex.
Breadth-first searchBFS visits vertices in rings of equal distance, so the first time it touches the solved state it has found a shortest path. The catch is the ring sizes: 18, 243, 3,240, 43,239… roughly ×13 per level.
Meeting in the middleBidirectional BFS grows one tree from the scramble and one from solved, and stops when they touch. Two trees of depth d/2 are far smaller than one of depth d, which is why it reaches scrambles that plain BFS cannot.
A* with a lower boundOne face turn moves at most 4 corners and 4 edges, so ⌈misplaced corners ÷ 4⌉ is a distance that can never be overestimated. A* uses it to expand promising vertices first, while still guaranteeing a shortest path.
COVE-3 (3×3 only)Our two-phase solver skips moves already ruled out by its distance bounds and verifies every returned solution. It compiles faster search tables after the first solve. Results are practical solutions, without a shortest-path guarantee. See the paper for matched-output comparisons and the memory tradeoff.