Package 'cayleyR'

Description

For each combination in a data frame of top results, runs a full cycle analysis and collects all states with their celestial coordinates into a single data frame.

Usage

analyze_top_combinations(top_combos, start_state, k)

Arguments

Value

Data frame with columns V1..Vn, operation, step, combo_number, nL, nR, nX, theta, phi, omega_conformal

Examples

combos <- data.frame(combination = c("13", "23"), stringsAsFactors = FALSE)
# result <- analyze_top_combinations(combos, 1:10, k = 4)

Description

Applies a sequence of shift and reverse operations to a permutation state. Operations can be specified as "1"/"L" (shift left), "2"/"R" (shift right), or "3"/"X" (reverse prefix). Tracks celestial coordinates.

Usage

apply_operations(state, operations, k, coords = NULL, compute_coords = TRUE)

Arguments

Value

List with components:

Examples

result <- apply_operations(1:10, c("1", "3", "2"), k = 4)
result$state

# Using letter codes
result <- apply_operations(1:20, c("L", "X", "R"), k = 4)
result$state

Description

Applies a sequence of permutation operations to multiple states simultaneously using matrix multiplication on the Vulkan backend.

Usage

apply_operations_batch_gpu(states_matrix, operations, k)

Arguments

Value

Numeric matrix (nrow x n) with transformed states

Examples

if (cayley_gpu_available()) {
  mat <- matrix(c(1,2,3,4,5, 5,4,3,2,1), nrow = 2, byrow = TRUE)
  result <- apply_operations_batch_gpu(mat, c("1", "3"), k = 4)
}

Description

Finds the shortest path between two permutation states using bidirectional breadth-first search. Expands from both the start and goal states simultaneously, meeting in the middle.

Usage

bidirectional_bfs(
  n,
  state1,
  state2,
  max_level,
  moves = NULL,
  k = NULL,
  group = NULL
)

Arguments

Details

The backward half of the search walks moves in reverse, so the path it returns may name moves outside moves: searching with left shifts alone still reports the right shift that undoes one. Inverses are taken from the group's whole alphabet for that reason, and a move the group cannot undo at all is an error rather than a silently wrong path.

Value

Character vector of operations forming the shortest path, or NULL if no path found within max_level

See Also

perm_group

Examples

# Find path between two small states
path <- bidirectional_bfs(5, 1:5, c(2, 3, 4, 5, 1), max_level = 5,
                          moves = c("1", "2", "3"), k = 3)
path

# the same search on a cube: undo a three-move scramble
g <- cube_group(3)
s <- group_apply(g, group_identity(g), "R U F")
bidirectional_bfs(54, s, group_identity(g), max_level = 4, group = g)

Description

Counts the number of positions where consecutive elements differ by more than 1 (breakpoints). Particularly effective for TopSpin puzzles where operations shift blocks and flip prefixes.

Usage

breakpoint_distance(start_state, target_state)

Arguments

Value

Integer, the number of breakpoints

Examples

breakpoint_distance(1:5, 5:1)
breakpoint_distance(1:5, 1:5)

Description

Creates an n x n permutation matrix (column-major, F32) that represents a single operation. When multiplied: new_state = state %*% P.

Usage

build_permutation_matrix(op, n, k)

Arguments

Value

Numeric vector of length n*n (column-major permutation matrix)

Description

Computes the angular distance on the celestial sphere between two points given as coordinate lists (each with a z component).

Usage

calculate_angular_distance_z(result1, result2)

Arguments

Value

Numeric, angular distance in radians

Examples

c1 <- convert_LRX_to_celestial(10, 5, 3)
c2 <- convert_LRX_to_celestial(1, 1, 2)
calculate_angular_distance_z(c1, c2)

Description

Computes the Manhattan distance from a reference state to every row in a table of reachable states, adds a difference column, and sorts by it.

Usage

calculate_differences(
  start_state,
  reachable_states_start,
  method = "manhattan",
  use_gpu = FALSE
)

Arguments

Value

Data frame sorted by difference (ascending)

Examples

df <- data.frame(V1 = c(1, 2), V2 = c(2, 1))
calculate_differences(c(1, 2), df)

Description

Computes the midpoint on the celestial sphere between two coordinate sets by averaging Cartesian unit-sphere positions and re-projecting.

Usage

calculate_midpoint_z(coords1, coords2)

Arguments

Value

List with theta, phi, z, z_bar, omega_conformal, nL, nR, nX

Examples

c1 <- convert_LRX_to_celestial(10, 5, 3)
c2 <- convert_LRX_to_celestial(1, 1, 2)
mid <- calculate_midpoint_z(c1, c2)
mid$theta

Description

Explores every state reachable from start_state by repeatedly applying the allowed operations, recording the graph distance of each state from the start. Unlike sparse_bfs, no pruning is applied: the whole reachable component is enumerated.

Usage

cayley_bfs_full(start_state, k = NULL, moves = NULL, group = NULL)

Arguments

Details

Celestial coordinates are a property of a path rather than of a state, since the same state can be reached by many different operation sequences. The nL, nR, nX counters reported here are those of the shortest path BFS happened to find first, and theta, phi, omega are derived from them via convert_LRX_to_celestial.

The search runs over a perm_group, so the same sweep enumerates a TopSpin ring or a Rubik's cube. Passing k without a group means TopSpin, exactly as before.

Value

Data frame with one row per reachable state:

See Also

cayley_graph_diameter, sparse_bfs, perm_group

Examples

d <- cayley_bfs_full(1:5, k = 3)
nrow(d)
table(d$dist)

# the same sweep over a cube subgroup: the middle slice, on its own
g <- cube_group(3, moves = c("M", "M'"))
d2 <- cayley_bfs_full(group_identity(g), group = g)
nrow(d2)

Description

Checks whether ggmlR is installed and Vulkan GPU is present.

Usage

cayley_gpu_available()

Value

Logical

Examples

cayley_gpu_available()

Description

Free GPU backend resources

Usage

cayley_gpu_free()

Value

Invisible NULL

Description

Lazily initializes the Vulkan backend. Safe to call multiple times.

Usage

cayley_gpu_init(device = 0L, force = FALSE)

Arguments

Value

Invisible backend pointer

Examples

if (cayley_gpu_available()) {
  cayley_gpu_init()
}

Description

Get GPU status information

Usage

cayley_gpu_status()

Value

List with availability, device info, and backend status

Examples

cayley_gpu_status()

Description

Computes the diameter of the Cayley graph component reachable from start_state, together with the pairs of states realising it and the eccentricity of each vertex.

Usage

cayley_graph_diameter(
  start_state,
  k = NULL,
  moves = NULL,
  group = NULL,
  method = c("all_pairs", "from_start"),
  max_pairs = Inf,
  verbose = FALSE
)

Arguments

Details

Two methods are available. "all_pairs" runs a BFS from every vertex and yields the true diameter and every diametral pair; its cost grows as the number of vertices times the cost of one BFS, which in practice limits it to permutations of roughly size 8 or below. "from_start" runs a single BFS and reports the eccentricity of start_state and the pairs ⁠(start_state, v)⁠ realising it; this equals the diameter only when the graph is vertex-transitive, but it scales to much larger graphs.

Value

List containing:

See Also

cayley_bfs_full

Examples

res <- cayley_graph_diameter(1:5, k = 3)
res$diameter
head(res$pairs_df)

# God's number for a small cube subgroup: the middle slice, on its own
g <- cube_group(3, moves = c("M", "M'"))
cayley_graph_diameter(group_identity(g), group = g,
                      method = "from_start")$diameter

Description

Identifies states that appear in both tables by comparing V-columns. Used for finding intersections between forward and backward searches.

Usage

check_duplicates(df1, df2)

Arguments

Value

Data frame of duplicate states with a source column, or NULL if none

Examples

df1 <- data.frame(V1 = c(1, 2), V2 = c(2, 1))
df2 <- data.frame(V1 = c(2, 3), V2 = c(1, 2))
check_duplicates(df1, df2)

Description

Multiplies individual permutation matrices into one combined matrix.

Usage

compose_permutation_matrix(operations, n, k)

Arguments

Value

Numeric vector of length n*n (combined permutation matrix, column-major)

Description

Parses a string of digits or space-separated numbers into an integer vector. Useful for converting operation sequences or state representations.

Usage

convert_digits(s)

Arguments

Value

Integer vector of parsed numbers

Examples

convert_digits("123")
convert_digits("1 5 4 3 2")
convert_digits("10 11 12 13")

Description

Maps cumulative operation counts (Left, Right, Reverse) to spherical celestial coordinates via stereographic projection.

Usage

convert_LRX_to_celestial(nL, nR, nX)

Arguments

Value

List with components:

Examples

coords <- convert_LRX_to_celestial(10, 5, 3)
coords$theta
coords$phi

Description

Builds the convex hull of a set of points in three dimensions and reports its triangular faces, surface area and volume. Implemented directly so the package keeps its single dependency on Rcpp; for the handful of points a landmark study produces, the incremental algorithm below is more than fast enough.

Usage

convex_hull_3d(pts, tol = 1e-09)

Arguments

Details

The construction is the classical incremental one. A non-degenerate starting tetrahedron is found first, then the remaining points are added one at a time: every face the new point can "see" (the point lies on the outer side of its plane) is removed, and the boundary of the hole left behind – the horizon – is joined to the new point. Points that see no face are already inside and are skipped.

Volume is the sum of the signed tetrahedra spanned by each face and an interior reference point; because every face is oriented outwards, the signs agree and the total is the enclosed volume.

Value

A list with components:

Examples

cube <- as.matrix(expand.grid(c(0, 1), c(0, 1), c(0, 1)))
h <- convex_hull_3d(cube)
h$area      # 6
h$volume    # 1

Description

Creates a C++ StateStore object for compact, incremental storage of permutation states with hash-indexed lookup.

Usage

create_state_store(perm_length, init_capacity = 10000L, group = NULL)

Arguments

Details

A store may be told which perm_group its states belong to. It needs this only to spell its own operation column: the codes it keeps are indices into the group's alphabet, and nothing but the group knows whether index 2 means a shift or a face turn. Without one, the legacy TopSpin spelling "1"/"2"/"3" is used.

Value

External pointer to StateStore (XPtr), with the group attached as an attribute so it stays alive as long as the store does

Examples

store <- create_state_store(6L)
state_store_size(store)

# a store that speaks cube
g <- cube_group(3)
cs <- create_state_store(54L, group = g)
state_store_perm_length(cs)

Description

Training a network to solve a cube without ever being shown a solution.

Details

The difficulty with learning a distance-to-solved is that nobody knows what it is. Labelling a state with the length of the scramble that produced it is the obvious thing to do and it is wrong: the scramble is one path to that state, not the shortest, so the label is an upper bound that gets looser the deeper the scramble goes, and a network trained on it learns the looseness along with the distance.

Autodidactic iteration sidesteps this. A state's target is not its scramble length but $\min_a (1 + v(child_a))$ — one move, plus whatever the network currently believes about the best of its children. That looks circular, and would be, except that a child which is already solved counts as zero no matter what the network says. States one move from solved therefore get an exact target immediately, their neighbours get an almost exact one from them, and correctness spreads outward as training goes on. This is why scrambles are drawn uniformly over depth and the loss carries no weighting: the ordering is in the structure of the targets, not the sampling.

Two networks

Value and policy are separate models here, not two heads on one trunk. ggml_fit trains a single output, so a shared trunk would need a multi-output loss that ggmlR does not yet have. The cost is a second forward pass per move at solve time; the benefit is that each network trains under the loss that suits it – mean squared error for a distance, cross-entropy for a choice of move – with no changes to ggmlR.

The frozen network

Targets are computed with a copy of the value network held fixed for the whole batch. Without it the targets move as the network moves and training chases itself; the copy is refreshed only once the running loss drops below loss_thresh, which is DeepCubeA's criterion and steadier than refreshing on a fixed schedule.

See Also

cube_adi_train, cube_adi_solve

Description

The search half of DeepCubeA. cube_adi_train learns a distance to solved; this walks the graph using that distance as its heuristic, and it is what turns an estimator into a solver.

Usage

cube_adi_astar(
  net,
  state,
  weight = 0.6,
  batch = 1000L,
  max_nodes = 1e+06,
  batch_size = 256L,
  verbose = FALSE
)

Arguments

Value

List with solved, path (move names), length, nodes (expanded) and iterations

Why not simply walk downhill

cube_adi_solve takes the best-looking child at every step and never reconsiders. That is enough near the goal, where the network is exact, and fails past it: a state whose true distance the network underrates draws the walk in, every child then looks worse than the parent, and the walk is stuck with no way back. A search keeps the alternatives it passed over on a list and returns to them when the branch it chose stops paying, so a wrong estimate costs time rather than the solve.

The weight

Nodes are ordered by $f = \lambda g + h$ — $g$ moves spent to reach the node, $h$ the network's guess at what remains. $\lambda = 1$ is textbook A*, which returns the shortest path the heuristic admits but expands far more nodes; $\lambda = 0$ ignores the cost so far and is pure greedy best-first, fast and prone to wandering. DeepCubeA runs around 0.6, buying much shorter runtimes for slightly longer solutions, and that is the default here. Note that the learned heuristic is not admissible in any case, so even $\lambda = 1$ carries no optimality guarantee — the weight trades length against time, it does not switch a guarantee on.

Why a batch

The expensive part of an iteration is not the queue, it is the forward pass. Scoring one node's children is a batch of n_moves, which leaves a GPU idle; so each iteration pops the batch best nodes at once, expands all of them, and scores every child in a single call. The cost of an iteration is then nearly flat in batch, and a wider batch means fewer of them. It also loosens the ordering — the 1000th-best node is expanded alongside the best — which is the same trade the weight makes, and the reason a very wide batch can lengthen solutions.

See Also

cube_adi_solve for the greedy walk

Description

Inverse of cube_adi_save. The group is rebuilt from the saved permutations, so the result is usable by cube_adi_solve and cube_adi_train without any of the code that first created it.

Usage

cube_adi_load(path, backend = "auto")

Arguments

Value

A cube_adi_net

See Also

cube_adi_save

Description

Two models over the same input: 96 sticker positions read as tokens through a shared-in-shape, separate-in-weights embedding, then a stack of dense layers. The value network ends in one linear unit (a distance), the policy network in one softmax unit per move.

Usage

cube_adi_model(
  group,
  embed_dim = 32L,
  hidden = c(1024L, 512L),
  arch = c("mlp", "resnet", "lstm", "gru", "transformer"),
  rnn_units = 256L,
  n_blocks = 4L,
  d_model = 64L,
  n_heads = 4L,
  ff_dim = NULL,
  encoding = c("sticker", "piece"),
  backend = "auto"
)

Arguments

Value

List with value and policy models, plus the group

Description

Writes the network to a directory: the two ggml models as their own files, and everything else as an RDS beside them.

Usage

cube_adi_save(net, path)

Arguments

Details

The group cannot be written directly — it lives behind an external pointer that means nothing in a later session. What is saved instead is the material to rebuild it: the state length and, for each move, the permutation it performs, read back by applying the move to the identity. Loading replays those through perm_group and gets the same group, so the saved network does not depend on the function that happened to build it.

Value

path, invisibly

See Also

cube_adi_load

Description

Walks downhill on the value network, one forward pass per move, refusing to revisit a state it has already stood on. Banning only the inverse of the last move is not enough – four of the same quarter turn also return to where they started – so the walk remembers where it has been, which covers every length of cycle with one rule.

Usage

cube_adi_solve(net, state, budget = 200L, use_policy = TRUE, batch_size = 256L)

Arguments

Value

List with solved, path (move names) and values

Description

Train Value and Policy by Autodidactic Iteration

Usage

cube_adi_train(
  net,
  iterations = 100L,
  batch_states = 10000L,
  max_depth = 20L,
  epochs = 1L,
  batch_size = 256L,
  loss_thresh = 0.5,
  refresh_every = NULL,
  verbose = TRUE
)

Arguments

Value

The network, with $history recording loss per iteration

Description

The learned sequences the solvers look up: 57 OLL cases, 21 PLL cases, and the handful of small algorithms layer-by-layer repeats. Returned as written in the literature, with the expanded quarter-turn word alongside.

Usage

cube_alg_table(
  which = c("oll", "pll", "lbl_cross", "lbl_edge_perm", "lbl_corner_perm",
    "lbl_corner_twist")
)

Arguments

Value

data.frame with name, notation, n_moves. The expanded words are on the "moves" attribute, one character vector per row.

See Also

cube_solve_cfop, cube_apply_word

Examples

oll <- cube_alg_table("oll")
nrow(oll)
head(oll)

Description

Applies moves written in standard notation. Half turns and wide turns are expanded into the package's quarter-turn alphabet, so "R U2 R'" is four moves, not three.

Usage

cube_apply_word(state, word)

Arguments

Value

Integer vector of 54 stickers, the state after the word

See Also

cube_word_order, cube_read_state

Examples

s <- cube_identity(3)
# a quarter turn of U, four times, is the identity
identical(cube_apply_word(s, "U U U U"), s)

Description

The second stage of Pochmann's centres, generalised: fill the layer that cube_lslice_cells names — the L face together with the column of each side face lying against it — so that every centre in it shows the colour of the face it sits on.

Usage

cube_build_lslice(state, n = NULL, max_rounds = 40L)

Arguments

Value

List with components:

Why a layer and not a face

Building face by face does not work, and the reason is measurable: every commutator that fills one face disturbs the four beside it, so a face finished early is taken apart later. A layer can be turned to the bottom and kept there, which is what makes the stage after this one safe.

Two stages, and both are needed

Bringing a piece into the layer and rearranging pieces already inside it are different problems, and one vocabulary does not answer both.

The ladder does the first: single moves of the whole alphabet, then pairs, then triples, taking the first word that raises the count. This is l_slice_insert of src/cube_centres.h, whose own note is that pairs carry the method — its worked example, an inner slice followed by a reversed U, runs 8, 8, 9, improving nothing on the first move, which is why words are judged whole rather than one move at a time.

Addressed three-cycles do the second. The ladder stops when the remaining pieces are inside the layer but in each other's places: no short word rearranges the layer's own contents, so the count simply stops improving, whatever the depth. A three-cycle moves exactly three centres and leaves the rest standing, and pointing one at named positions closes what the ladder cannot.

Measured over ten scrambles at each size, the ladder alone finished 2 of 30 and the two together 30 of 30 — reaching 17.9 of 20 on a 5x5x5 by itself and 20 of 20 with the cycles.

What the cycles need

A commutator for every moving orbit, and the 5x5x5 is the case that shows why: its plus centres are cycled only through the central slice. While that was excluded from cube_centre_cycles on the grounds that a central turn rotates the cube, half the pieces had no tool and builds stalled on them.

The triple of faces also has to be one a rotation can deliver. The commutators act on faces 0, 2 and 5, two of which are opposite, and rotation preserves adjacency — so twelve of the twenty triples are reachable and eight are not. In practice only reachable ones are ever wanted, which cube_centres.h reports measuring too.

See Also

cube_lslice_cells, cube_centre_cycles, cube_centre_shots

Examples

set.seed(1)
g <- cube_group(4)
s <- group_apply(g, group_identity(g),
                 sample(cube_move_names(4), 6, replace = TRUE))

r <- cube_build_lslice(s)
r$built
length(r$path)

Description

On an odd cube the middle layer of an axis carries that axis's fixed centres, so turning it is a rotation of the cube rather than a move within it. A method that means to keep a face where it is must leave these alone.

Usage

cube_central_moves(n)

Arguments

Details

Which moves these are is found by asking, not by counting layers: a move is central exactly when it disturbs the six fixed centres. An even cube has no fixed centres and so no central moves, and the answer is the empty vector.

Value

Character vector of move names, empty on an even cube.

See Also

cube_centre_shots, cube_centre_structure

Examples

cube_central_moves(5)   # 2x, 2y, 2z and their inverses
cube_central_moves(4)   # none: an even cube has no middle layer

Description

How many centre pieces show the colour of the face they sit on, counted per face. A face is finished when its count is the number of centres a face has at that size — four on a 4x4x4, nine on a 5x5x5, one on a 3x3x3.

Usage

cube_centre_counts(state, n = NULL, by_orbit = FALSE)

Arguments

Details

The count compares a piece's colour against the face it began on, so it is only meaningful while the cube has not been turned as a whole. That is the state generate_state hands over and the one cube_solve_centres is given.

Value

With by_orbit = FALSE, an integer vector of six counts in face order U R F D L B. With by_orbit = TRUE, a data.frame of orbit, face, home and of — how many are home out of how many.

See Also

cube_solve_centres, cube_centre_structure

Examples

cube_centre_counts(cube_identity(4))
cube_centre_counts(cube_identity(5))

# the three orbits of a 5x5x5, seen apart
cube_centre_counts(cube_identity(5), by_orbit = TRUE)

Description

The commutator that moves three centres and nothing else. Steps that fill a face leave the centres in arrangements a swap cannot reach — a three-cycle is an even permutation and a swap is odd — so a method needs this shape as well as the shots.

Usage

cube_centre_cycles(n, all = FALSE)

Arguments

Value

A data.frame with columns word (the eight moves, space separated), orbit (which centre orbit it cycles), faces (the three faces involved, comma separated, ascending) and slots (the slot on each, in that same face order).

Derived, and wider than the original

src/cube_centres.h carries one such commutator, written out for a 4x4x4: 1x U 2x' U' 1x' U 2x U', cycling a centre between faces 0, 2 and 5. The same shape is searched here instead — over every ordered pair of inner slices, about all three axes, conjugated by each of the six face turns. Each candidate is checked to move exactly three centres of one orbit before it is kept, so what comes back is a three-cycle by measurement rather than by construction.

The result is wider than the file's in two ways. Every moving orbit gets its own commutators, not just the one a 4x4x4 has; and they reach all twenty triples of faces rather than the single triple 0, 2, 5 that one fixed word acts on. Both matter to a method, which has to cycle whichever three faces the cube presents.

The central slice belongs in the search

An earlier version excluded cube_central_moves on the grounds that turning the middle layer of an odd cube turns the whole cube. That is true of the move by itself and false of a commutator built from it: only the whole word is judged, and the frame it disturbs in the middle it puts back at the end. Measured on a 5x5x5, 1644 of 2592 candidate words leave the fixed centres exactly where they were.

Excluding it cost the 5x5x5 an entire orbit. Its plus centres are cycled by 1x U 2x' U' 1x' U 2x U' and nothing else of this shape — one character from the corner centres' own word, and that character is the central slice.

See Also

cube_centre_shots, cube_centre_structure, cube_central_moves

Examples

# a 4x4x4 has one moving orbit, cycled between many triples of faces
cyc4 <- cube_centre_cycles(4)
unique(cyc4$orbit)
length(unique(cyc4$faces))

# a 5x5x5 has two, and the plus centres need the central slice
cyc5 <- cube_centre_cycles(5)
unique(cyc5$orbit)

Description

What a method needs to know about centres before it can build them: which stickers are centre stickers, which orbit each belongs to, where it sits on its face, and where every slice turn sends it. All of it read off cube_moves and cube_orbits rather than written down per size.

Why this is derived

The 4x4x4 centre solver in src/cube_centres.h carries its slice table as six hand-measured blocks of eight steps. That table is correct, and it is also the reason the file solves one size: the numbers say f*16 + local, the slots run 1 to 4, and both facts are assumptions about a 4x4x4 rather than about cubes.

Nothing in that table is independent of the permutations, though. A slice turn is a permutation; asking it where each centre sticker goes reproduces the hand table exactly — all six blocks, at n = 4 — and asks the same question of any other size. That equality is checked in the tests, so the generic version is held to the hand-measured one rather than merely believed.

Slots

A face carries several centre stickers of the same orbit, and a method has to name them. They are numbered along the cycle of that face's own turn: slot 1 is the lowest sticker index in the group, slot 2 is where a quarter turn sends it, and so on. Numbering by the turn rather than by reading order means slot arithmetic is the same on every face and at every size — a quarter turn always adds one, modulo the cycle length.

See Also

cube_centre_structure, cube_slice_map, cube_orbits

Description

The centres never move, which is what makes a face's name mean anything: the U face is the face whose centre is the U centre, whatever has happened to the rest of the cube.

Usage

cube_centre_positions()

Value

Integer vector of 6 sticker positions (1-based)

See Also

cube_identity

Examples

cube_centre_positions()
s <- cube_apply_word(cube_identity(3), "R U R' U'")
# centres are where they always were
all(s[cube_centre_positions()] == cube_centre_positions())

Description

The generic form of the eight shots that src/cube_centres5.h lists by hand for a 5x5x5. A shot is a conjugation — a slice turn, a turn of the working face, then the slice back — and what makes it usable is what it does not do: the kept face's centres come back exactly where they were, so whatever has already been built there survives however many shots are fired afterwards.

Usage

cube_centre_shots(n, keep_face = NULL, turn_face = "U")

Arguments

Value

A data.frame with columns word (the three moves, space separated), to_face (the face centres are carried to), n_moved (how many centre stickers move) and orbits (which centre orbits they belong to, comma separated). No rows if the size has no moving centres.

What is required of a shot

Three conditions, each checked against the permutations rather than assumed. The kept face must be untouched. Some centre must actually cross between faces, which is what rules out the conjugations by a turn of the working face's own axis — they stir that face without emptying it. And the slice must not be a central one, since on an odd cube that turns the whole cube and moves the kept face out from under the method (cube_central_moves).

See Also

cube_central_moves, cube_centre_structure

Examples

# a 5x5x5 has eight, two onto each side face
s <- cube_centre_shots(5)
table(s$to_face)

# each carries both moving orbits at once, which is why the two are solved
# together rather than in turn
unique(s$orbits)

Description

One row per centre sticker: which face it is on, where on that face, which orbit it belongs to and which slot of its (face, orbit) group it occupies.

Usage

cube_centre_structure(n)

Arguments

Details

A centre piece carries exactly one sticker, so pieces and stickers are the same thing here and the table can be indexed either way.

Value

A data.frame with columns sticker (1-based index into the state vector), face (0 to 5), local (0-based position within the face), orbit (as numbered by cube_orbits) and slot (1-based, along the face-turn cycle).

See Also

cube_slice_map, cube_centre_map_family

Examples

# a 4x4x4 has one centre orbit, four per face
cs <- cube_centre_structure(4)
table(cs$orbit)

# a 5x5x5 has three: two of 24 and the six fixed centres
table(cube_centre_structure(5)$orbit)

# the fixed centres of an odd cube are alone in their group
cs5 <- cube_centre_structure(5)
table(cs5$slot[cs5$orbit == max(cs5$orbit)])

Description

A cube state can record, for each sticker, either the colour it shows or the place it belongs in. The package works in positions — a state is a permutation of 1:(6n^2), and the solvers and searches all read it that way — while most outside sources, Kaggle's Santa 2023 among them, record colours.

Usage

cube_colours(state, n = NULL)

cube_colour_state(state, n = NULL)

Arguments

Details

cube_colours goes from positions to colours, which always works and loses information. cube_colour_state goes back, which works only when the colours happen to determine the state.

Value

cube_colours returns $6n^2$ colours numbered from 0, one per sticker, in face order U R F D L B. cube_colour_state returns a permutation of 1:(6n^2).

When colours are enough

On a 2x2x2 or a 3x3x3 every piece carries a different set of colours, so a colouring names exactly one state and the conversion is exact.

From 4x4x4 up it is not. The four wings of an edge share their two colours, and the centres of a face share one, so a colouring cannot say which of them is which — and the number of states it stands for grows quickly with $n$. cube_colour_state still returns a state, choosing among the identical pieces in the order they are numbered, but it warns; the state it returns shows the right colours and is not otherwise the state you started from.

See Also

cube_santa_state for the same journey across notations, cube_is_colour_solved, cube_pieces

Examples

set.seed(1)
s <- generate_state(group = cube_group(3), n_moves = 10)

# positions to colours and back is exact on a 3x3x3
identical(cube_colour_state(cube_colours(s)), s)

# a solved cube is six blocks of one colour
table(cube_colours(cube_identity(3)))

Description

The six slice-flip-slice words the 4x4x4 solver uses, written in the package alphabet for a cube of side n. A slice brings two pieces of one edge together, a face turn flips one of them, the slice goes back.

Usage

cube_edge_algs(n)

Arguments

Value

A character vector of six words, each a space-separated sequence of package moves.

Why these six

They are the set measured in src/cube_edges.h, which records for each one its length, how many pairs it breaks and how many slots it touches. All six leave the centres built, which is what makes them safe to run after the centre stage. The last is the parity case — it swaps two pieces of one edge rather than permuting whole edges.

What changes with size

Only the wide turns, and only in which numbered slice they name. The words are stated here in the sources' own notation (Rw, Dw, Uw) and expanded through cube_wide_turn, so a single statement covers every size instead of one transcription per cube. At n = 4 the expansion reproduces the six constants in the reference file exactly, which the tests check.

Verified at n = 4 against the reference's own table: from a solved cube the six leave 9, 9, 10, 10, 10 and 8 edges whole — that is 3, 3, 2, 2, 2 and 4 pairs broken, as the reference records.

See Also

cube_wide_turn, cube_edge_counts

Examples

cube_edge_algs(4)[1]
cube_edge_algs(5)[1]     # the same algorithm, the slice renumbered

Description

The count a pairing stage ranks its moves by, and the per-edge breakdown behind it. An edge is whole when every piece sitting on it shows the same pair of colours — on a 4x4x4 that is two wings agreeing, on a 5x5x5 three pieces, on an odd cube the middle piece counts with its wings.

Usage

cube_edge_counts(state, n = NULL, structure = NULL)

Arguments

Details

This is the rule cube_is_reduced applies to decide the whole cube; here it is asked one edge at a time, because a solver that can only see "reduced or not" has nothing to rank a candidate move by.

Value

A list with whole (how many of the twelve edges are whole), total (twelve) and by_edge, a logical vector one entry per edge.

See Also

cube_edge_structure, cube_is_reduced

Examples

cube_edge_counts(cube_identity(5))$whole      # 12

# an inner slice splits the edges it touches
s <- cube_identity(5)
cube_edge_counts(s[cube_moves(5)[["1x"]]])$whole

Description

The permutation a single move induces on the edge slots: which slot each piece's contents lands in. This is the table an edge solver reads instead of searching, and it is the generic form of slot_maps() in src/cube_edges.h.

Usage

cube_edge_map(n, move, structure = NULL)

Arguments

Details

Only the slots the move actually disturbs are listed. Measured at n = 4 and n = 5, an outer turn moves 4(n - 2) slots and never splits an edge, while a slice moves 4 and splits all four it touches — see cube_edge_map_family for why that difference is the whole mechanism of pairing.

Value

A data.frame with one row per disturbed slot and columns from_piece, from_edge, from_pos, to_piece, to_edge, to_pos and splits — the last TRUE when the move carries this piece off an edge whose other pieces it leaves behind.

See Also

cube_edge_structure, cube_slice_map

Examples

cube_edge_map(4, "U")     # eight slots, four whole edges
cube_edge_map(4, "1x")    # four slots, four edges split

Description

What a method needs to know about edges before it can pair them: which pieces are edge pieces, which of the twelve cube edges each sits on, where along that edge it lies, and where every turn sends it. All of it read off cube_pieces and cube_moves rather than written down per size.

Why this is derived

The 4x4x4 edge solver in src/cube_edges.h carries its slots as a hand-measured table of twenty-four sticker pairs, ordered "the twelve edges by face pair, A then B". That table is correct, and it is also the reason the file solves one size: twenty-four is a fact about a 4x4x4, and so is the pair of names A and B. A 5x5x5 puts three pieces on every edge, a 7x7x7 puts five, and neither has halves to call A and B.

Nothing in the table is independent of the geometry, though. An edge piece is a piece with two stickers; the edge it belongs to is the pair of faces it touches; its place along that edge is the one coordinate that is not pinned to a face. Asking those three questions of cube_pieces reproduces the hand table at n = 4 and asks the same question of any other size. That equality is checked in the tests, so the generic version is held to the hand-measured one rather than merely believed.

How many pieces an edge holds

Measured, not assumed: n = 3 through n = 7 give 12 cube edges at every size, holding n - 2 pieces each — 1, 2, 3, 4, 5. The pieces fall into floor((n - 1) / 2) orbits, and on an odd cube the last of those holds the 12 middle edges, one per cube edge, sitting on the symmetry plane. Those are the pieces that behave like the edges of a 3x3x3.

Why outer turns cannot pair anything

The mechanism the 4x4x4 solver is built on generalises exactly. Measured at n = 4 and n = 5 over the whole alphabet:

• the six OUTER turns move 4(n-2) slots and touch 4 cube edges, none of them partially — an edge travels whole, so an outer turn can neither pair anything nor break a pair;

• every SLICE moves 4 slots across 4 cube edges, all four partially — it carries one piece off each edge and leaves the rest. That mismatch is the entire mechanism of pairing, and it is also why a slice on its own wrecks the centres.

So a slice has to be wrapped: open with it, work with outer turns, close with its inverse. That is the same shape the l-slice stage of the centres used.

See Also

cube_edge_structure, cube_edge_map, cube_pieces, cube_centre_structure

Description

One row per edge piece: which of the twelve cube edges it sits on, where along that edge it lies, which orbit it belongs to and which stickers it carries.

Usage

cube_edge_structure(n)

Arguments

Details

An edge piece carries exactly two stickers, which is what distinguishes it from a corner (three) and a centre (one). See cube_edge_map_family for why this is derived rather than tabulated per size.

Value

A data.frame with one row per edge piece and columns piece, edge, face_lo, face_hi, pos, slot, orbit, label, sticker_a and sticker_b — the last two 1-based indices into the state vector.

Naming an edge

A cube edge is named by the two faces it lies between, as face_lo and face_hi with face_lo < face_hi, so the name does not depend on which way the edge is read. The edge column numbers those twelve pairs in ascending order, and is stable at every size.

Naming a place along an edge

pos is the coordinate that runs along the edge, from 1 to n - 2. slot is the same thing numbered from the nearer end, from 1 up, so that pieces which are mirror images of each other across the middle of the edge share a slot number; on an odd cube the middle piece is the only one of its slot. Pieces of one edge with the same slot are the ones a solver has to tell apart, and pos is what tells them.

See Also

cube_edge_map, cube_pieces

Examples

e <- cube_edge_structure(4)
nrow(e)                  # 24 wings, two to an edge
table(e$edge)            # twelve edges, two pieces each

e5 <- cube_edge_structure(5)
nrow(e5)                 # 36: 24 wings and 12 middles
table(e5$orbit)

Description

The third stage of Pochmann's centres, generalised. With a layer built by cube_build_lslice and turned to the bottom, the shots of cube_centre_shots fire pieces off U onto the side faces they belong to. Every shot leaves D untouched, so what has been built and turned down survives however many shots follow.

Usage

cube_empty_u_slice(state, n = NULL, max_shots = 200L)

Arguments

Value

List with components:

How a shot is chosen

The piece is named first and the shot chosen for it, not the other way round: a centre on U belonging to a side face, a shot firing at that face, and the number of U turns that bring the piece to that shot's entry slot.

Asking instead for a shot that raises the count refuses the ones that work. Measured on the positions where an earlier version stalled: every foreign piece had two shot-and-setup pairs that sent it home, and not one of the thirty-two combinations raised the total. A piece going home displaces one that was there already, and the count recovers a shot or two later.

A shot has a second use as well. It is a 4-cycle — it takes a piece off U and pulls another up in exchange — so once U holds only pieces belonging to U, the way on is to spend one to bring up another. Such a reload lowers the count by design and is judged by the ammunition instead: how many pieces on U belong to neither the top face nor the bottom.

What it reaches

Measured over five scrambles of a 5x5x5, it takes the cube from 25 centres home to about 36 of 48, closing one face. It does not finish: the last two or three pieces on U can be placed only at the cost of a side face that is unfinished too. Pochmann answers that with a tilt — turning an unfinished face up to U — but a tilt is only legal once three faces are done, and from one it cannot be reached. Widening the guard was tried and lost ground (30.4 centres against 35.4), and so was ranking by a target face (36.2).

See Also

cube_build_lslice, cube_centre_shots, cube_centre_counts

Examples

set.seed(1)
g <- cube_group(5)
s <- group_apply(g, group_identity(g),
                 sample(cube_move_names(5), 4, replace = TRUE))

lay <- cube_build_lslice(s)
down <- group_apply(g, lay$state, cube_expand_word("z'", 5))
r <- cube_empty_u_slice(down)
r$count
r$faces

Description

Published algorithms are written with half turns (R2), wide turns (r), and whole-cube rotations (x, y, z). The package's alphabet has none of those: it is quarter turns of single layers. This is the translation.

Usage

cube_expand_alg(notation)

Arguments

Details

Rotations are the interesting case. A rotation in a printed algorithm is an instruction to the reader — turn the cube, and read what follows from where it now is — so it is expanded by renaming the letters after it, not by turning the cube and leaving them alone. Expanding it the other way silently produces a different algorithm, which is what happened to the published V-perm before this was written.

Value

Character vector of move names in the package alphabet

See Also

cube_alg_table, cube_apply_word

Examples

cube_expand_alg("R U2 R'")        # the half turn becomes two moves
cube_expand_alg("y R U R'")       # the rotation renames what follows

Description

The alphabet a cube is generated in turns one layer at a time, because that is what keeps the metric honest: $6n$ moves, half turns written out, so a shortest path counts quarter turns. Speedcubing writes in a larger vocabulary. Rw turns the two layers nearest the right face together, 3Rw turns three, and x turns the whole cube. Reduction methods for the 4x4x4 and up are published in that vocabulary and in no other.

Usage

cube_expand_move(name, n)

cube_expand_word(word, n)

cube_wide_move(name, n)

cube_wide_word(word, n)

Arguments

Details

These functions translate it. cube_expand_move takes one such name and returns the layer moves it stands for; cube_expand_word does a whole algorithm; cube_wide_move returns the single permutation the name performs. Nothing here enters the generating set — Rw is a word of two moves, not a move — so the metric and every diameter measured in it are untouched.

Value

cube_expand_move and cube_expand_word return a character vector of layer moves from the cube's own alphabet; cube_wide_move returns a permutation of 1:(6n^2).

The notation

A trailing prime inverts and a trailing 2 doubles, as usual, and a half turn expands into two quarter turns because the alphabet has no other way to say it.

A block move counts slices, and the count is bounded at both ends by the WCA regulations (12a2, 12a2+): strictly more than one and strictly fewer than $n$. One slice is a face turn and drops the w; every slice is a rotation and is written x, y or z. So "1Rw" names nothing on any cube, "4Rw" names nothing on a 4x4x4, and both are refused — otherwise one move would have two spellings. Rw and 2Rw are the same move, as the regulations say.

The senses are the ones the literature uses: x follows R, y follows U, z follows F. Lower-case r is accepted as a synonym for Rw, which is how many sources write it.

Why not generators

A wide turn could be added to the alphabet instead, and then Rw would cost one move rather than two. That would change what a shortest path is, and the numbers this package reports — diameters, level sizes, the distance any search returns — would no longer be comparable with the ones it reported before, nor with the published quarter-turn figures. Keeping the vocabulary outside the alphabet costs nothing and avoids all of that.

See Also

cube_moves, cube_move_names, cube_group

Examples

# on a 4x4x4 a wide turn is two layers
cube_expand_move("Rw", 4)

# three of them, and the whole cube
cube_expand_move("3Rw", 4)
cube_expand_move("x", 4)

# a single inner layer, counted in from the face
cube_expand_move("3R", 5)

# a whole algorithm at once
cube_expand_word("Rw U Rw'", 4)

# and the permutation it performs
p <- cube_wide_move("Rw", 4)
length(p)

Description

Builds the cube as a perm_group, so every search function in the package runs over it: the same BFS and the same store that work on TopSpin work here, and nothing about them knows the size of the cube.

Usage

cube_group(n, moves = NULL)

Arguments

Value

An object of class perm_group

See Also

cube_group for the 3x3x3 with half turns as single moves, cube_nnn, perm_group

Examples

g <- cube_group(3)
g
group_moves(g)

# face turns only: the slices left out
cube_group(3, moves = c("U", "U'", "R", "R'", "F", "F'",
                        "D", "D'", "L", "L'", "B", "B'"))

# a 2x2x2 is small enough to walk about in
g2 <- cube_group(2)
group_order(g2, "R")
group_order(g2, "R U")

Description

Solved State of an N x N x N Cube

Usage

cube_identity(n)

Arguments

Value

Integer vector 1:(6*n^2)

See Also

cube_is_colour_solved

Examples

length(cube_identity(3))
length(cube_identity(4))

Description

A sticker's colour is the face it started on, so this asks whether each face now carries stickers of one colour — not whether they are back in their original positions.

Usage

cube_is_colour_solved(state, n = NULL)

Arguments

Details

The distinction only appears once slice turns are in play. Face turns leave the centres alone, so from cube_identity they can never reach a state that is one-coloured without being the identity outright. Slices do move the centres, and then a cube turned bodily in space is solved by any reasonable reading while its sticker vector is not 1:6n^2.

Value

Logical

See Also

cube_identity, cube_nnn

Examples

cube_is_colour_solved(cube_identity(3))

# a face turn breaks it
g <- cube_group(3)
cube_is_colour_solved(group_apply(g, cube_identity(3), "R"))

# turning every layer of one axis is turning the whole cube: the colours
# stay solved, but the stickers are no longer where they started
s <- group_apply(g, cube_identity(3), c("R", "M'", "L'"))
cube_is_colour_solved(s)
identical(s, cube_identity(3))

Description

Reduction is the state a large cube has to reach before a 3x3x3 method can touch it: every face's centres one colour, so a face acts as one, and the wings of every edge a matching group, so an edge acts as one. A cube in that state is a 3x3x3 with fat pieces.

Usage

cube_is_reduced(state, n = NULL)

Arguments

Details

What this does not ask is where anything is. A solved cube turned by one U is still reduced — the centres are whole and the pairs are together, they are merely in the wrong place, and putting them right is the 3x3x3's job rather than the reduction's. Asking for position here is the easy mistake and it makes the test reject cubes that are plainly reduced.

Value

TRUE if the cube is reduced.

Any size

Nothing in the test is about a 4x4x4 beyond how many pieces there are. A face has $(n-2)^2$ centres rather than four and an edge has $n-2$ wings rather than two, and both numbers come from cube_pieces. An odd cube reduces too: its middle edges and fixed centres are groups of one, which pass the test by having nothing to disagree with.

A 3x3x3 is reduced in every state, and that is the right answer rather than a degenerate one — there is nothing to reduce.

See Also

cube_solve4, cube_pieces, cube_centre_counts

Examples

s <- cube_identity(4)
cube_is_reduced(s)

# a turned face is still reduced: the pieces are whole, just not home
m <- cube_moves(4)
names(m) <- cube_move_names(4)
cube_is_reduced(s[m[["U"]]])

# an inner-layer turn is not: it splits the pairs and the centres
cube_is_reduced(s[m[["1x"]]])

# a 5x5x5 works the same way
cube_is_reduced(cube_identity(5))

Description

The fifth solver in the package and the only one that is not a human method. The other four place pieces by rule or by table and stay inside what a person could do by looking; this one searches, and pays for the short solution in a way no cuber could.

Usage

cube_kociemba(state, max_depth1 = 12L, max_depth2 = 18L, node_budget = 5e+07)

Arguments

Value

List with path, the character vector of moves, and found, whether a solution was reached within the limits. The same shape as cube_solve_cfop and the other 3x3x3 solvers, so the five can be used interchangeably.

How this differs from the published algorithm

Kociemba's own two-phase algorithm does not stop at the first solution. It keeps searching phase 1 for other ways into the subgroup and keeps whichever leaves phase 2 shortest, which is how it reaches around twenty moves; the two phases are cheap enough to run many times over. This takes the first entry phase 1 finds, so a cube one quarter turn from solved comes back as R R R rather than R-prime. The prune tables are hash tables grown on demand rather than full coordinate tables. Short rather than shortest, in other words, and the demo names it KociembaMod for that reason.

Where the search machinery comes from

The engine underneath – the canonical move automaton, the hash prune table grown to half the depth about to be searched, the two-level cutoff that abandons a whole move class when the bound is hopeless by more than one – follows twips (https://github.com/cubing/twips) by Lucas Garron and the cubing.js authors, MPL-2.0. The phase definitions and the piece reading are this package's own, built on its existing sticker geometry.

The algorithm is the observation that a cube is much easier to solve if you first make it easy. The subgroup $G_1 = \langle U, D, L^2, R^2, F^2, B^2\rangle$ is the set of states reachable without ever quarter-turning L, R, F or B, and it is small: about 20 million states against 43 quintillion. Getting into it is the first phase; finishing inside it is the second.

What makes a state a member of $G_1$ is three things, and each is exactly what the excluded quarter turns would break: every edge oriented, every corner oriented, and the four E-slice edges somewhere in the E slice — though which of the four sits where does not matter yet. Phase 1 searches for that and nothing else, on a coordinate that has thrown the rest of the cube away.

Why the moves are counted twice over

The returned path is in the package's quarter-turn alphabet, so a half turn comes back as two moves. Inside the solver it is one: phase 2 is generated by $\langle U, D, L^2, R^2, F^2, B^2\rangle$ and a half turn there is a single step of the group, not a shorthand for two. Move cost is a property of the phase rather than of the package, which is what lets one search engine serve both phases.

Centres

Slice moves turn the centres, and a piece is identified by its colours read against them — so on a cube whose centres have moved, every cubie reads as the wrong one. As in the four human methods, the cube is turned bodily back first and the rotation is returned as part of the path, so the answer applies to the cube as it was handed over.

See Also

cube_solve_cfop and cube_solve_lbl for the methods that look at the cube, cube_kociemba_report for what the last solve did

Examples

set.seed(42)
s <- generate_state(group = cube_group(3), n_moves = 10)

res <- cube_kociemba(s)
res$found
length(res$path)

# it really solves it
moves <- cube_moves(3)
names(moves) <- cube_move_names(3)
for (mv in res$path) s <- s[moves[[mv]]]
identical(s, cube_identity(3))

Description

The tables grow themselves as the search asks for depth, so nothing needs calling before cube_kociemba. This exists for the caller who would rather pay that cost somewhere they expect it than inside the first solve.

Usage

cube_kociemba_init(
  table1 = 4194304,
  depth1 = 0L,
  table2 = 16777216,
  depth2 = 0L
)

Arguments

Value

Invisibly NULL, called for its effect.

See Also

cube_kociemba

Examples

cube_kociemba_init()

Description

"No solution" and "ran out of budget" are different facts, and a caller that cannot tell them apart goes looking for a fault in the cube when the answer is to raise a limit. This reports the outcome of each phase of the most recent cube_kociemba call, and how many nodes it visited.

Usage

cube_kociemba_report()

Value

List with phase1, phase2 — each one of "found", "no_solution" or "exhausted" — and phase1_nodes, phase2_nodes.

See Also

cube_kociemba

Examples

set.seed(42)
s <- generate_state(group = cube_group(3), n_moves = 10)
cube_kociemba(s)
cube_kociemba_report()

Description

The three reduction phases of cube_kociemba4_reduce, and then the cube — now a 3x3x3 with fat pieces — handed to cube_kociemba. That is the fourth phase, and it is the only one that lives on this side of the C++ boundary: the reduced cube is squeezed from 96 stickers to 54, solved, and the answer lifted back to 4x4x4 moves.

Usage

cube_kociemba4(
  state,
  max_depth1 = 10L,
  max_depth2 = 12L,
  max_depth3 = 14L,
  node_budget = 5e+07,
  progress_every = 0,
  stop_at_first = TRUE,
  budget_steps = c(0.1, 1),
  max_orientations = length(.cube4_orientations)
)

Arguments

Details

The same limits apply as to the reduction — see What this reaches today in cube_kociemba4_reduce. Where this returns a path it is a short one, a few dozen moves against the several hundred cube_solve4 takes; where it returns nothing, cube_solve4 is what to call.

Value

List with components:

See Also

cube_kociemba4_reduce, cube_kociemba4_report, cube_solve4

Description

Reduction is what an even cube has to reach before a 3x3x3 method can touch it: the four centres of a face one colour, so the face acts as one, and the two wings of every edge together, so the edge acts as one. This searches for it, in the three phases described in src/kociemba4.h: the F/B centres, then the other four faces' centres, then the wings.

Usage

cube_kociemba4_reduce(
  state,
  max_depth1 = 10L,
  max_depth2 = 12L,
  max_depth3 = 14L,
  node_budget = 5e+07,
  progress_every = 0,
  prune_depth_bonus = 0L,
  orientations = .cube4_orientations,
  stop_at_first = TRUE,
  budget_steps = c(0.1, 1),
  max_orientations = length(orientations)
)

Arguments

Value

List with path, the moves taking the cube to a reduced state, and found, whether the search got there within the limits. The same shape the package's other solvers return, so a caller can read $found without knowing which one it called.

Parity

Reduction can leave a cube in a state no 3x3x3 reaches — the wings paired and the corners solved with the permutation odd — and the package's other 4x4x4 solver, cube_solve4, meets that at the end and repairs it with an inner-layer algorithm. Here it cannot arise: the parity is carried in phase 3's coordinate, so a solution that would leave the cube parity-odd is not a solution to the phase and the search never returns it. No repair step follows, because there is nothing to repair.

What this reaches today

Phase 3's coordinate grows by about a factor of fifteen per level and its search is the deep one. Measured over five scrambles at each length with the default budget: five moves reduces every time in about a tenth of a second, six moves three times in five, seven moves once in five. Past that the phase spends its budget and the function returns nothing — which cube_kociemba4_report distinguishes from "no solution exists". Raising node_budget buys some of this back at a cost in time. For a cube from a full scramble, cube_solve4 is the one that finishes; it takes many more moves and always gets there.

See Also

cube_kociemba4 for the whole solve, cube_is_reduced for the test this aims at, cube_solve4 for the solver that always finishes

Description

As cube_kociemba_report is to the 3x3x3, so this is to the three reduction phases: which of them finished, which ran out, and what each cost. A phase that reports "exhausted" is one to raise node_budget for; "no_solution" within the depth given is a different fact and wants max_depth raised instead.

Usage

cube_kociemba4_report()

Details

Phase 4 does not appear here. It is cube_kociemba on the squeezed cube, and cube_kociemba_report is what reports it.

Value

List with phase1, phase2, phase3 — each one of "found", "no_solution" or "exhausted" — and phase1_nodes, phase2_nodes, phase3_nodes.

See Also

cube_kociemba4_reduce, cube_kociemba4

Description

The generator's own vocabulary, for when naming a layer is less convenient than pointing at it — on a 5x5x5, say, where the inner layers have no letters anyone agrees on.

Usage

cube_layer_move(n, axis, layer, turns = 1L)

Arguments

Value

Integer vector of length $6n^2$, the permutation

See Also

cube_moves

Examples

# on a 3x3x3, layer 3 about y is the U face
identical(cube_layer_move(3, axis = 2, layer = 3, turns = 3),
          cube_moves(3)[["U"]])

# layer 2 about x is the M slice
identical(cube_layer_move(3, axis = 1, layer = 2, turns = 1),
          cube_moves(3)[["M"]])

Description

Building centres face by face does not work: the commutators that fill one face disturb the four beside it, so a face finished early is taken apart later. Pochmann's method builds a layer instead — one face together with the column of each side face lying against it — because a layer can be turned to the bottom and kept there.

Usage

cube_lslice_cells(n)

cube_free_moves(n)

Arguments

Details

cube_lslice_cells is that layer, and cube_free_moves is the vocabulary that may be used once it is built: the single moves that leave every one of its centres where it stands.

Value

For cube_lslice_cells, a data.frame of the layer's centres with columns sticker, face, orbit and slot. For cube_free_moves, a character vector of move names.

Derived, not tabulated

src/cube_centres.h writes the layer out as twelve hand-measured cells and names the free moves in a comment. Both are read off the permutations here instead: the layer is what a wide L turn moves, and a move is free when it moves none of it. At n = 4 the two agree exactly — twelve cells, and the free moves R, R'}, \code{2x}, \code{2x' — which the tests check. At other sizes the same questions have bigger answers: twenty cells on a 5x5x5, thirty-two on a 6x6x6.

See Also

cube_centre_shots, cube_centre_structure

Examples

# the twelve centres of a 4x4x4's l-slice: all of L, two of each side face
table(cube_lslice_cells(4)$face)

# what may be turned once it is built
cube_free_moves(4)

# the same questions at another size
nrow(cube_lslice_cells(5))
cube_free_moves(5)

Description

Move Names of an N x N x N Cube

Usage

cube_move_names(n)

Arguments

Value

Character vector of $6n$ move names, in table order

See Also

cube_moves

Examples

cube_move_names(2)
cube_move_names(3)
cube_move_names(4)

Description

The $6n$ quarter turns of a cube of side $n$, as permutations of its $6n^2$ stickers. Generated from the geometry rather than tabulated, so the same rule gives the 2x2x2, the 3x3x3 and anything larger.

Usage

cube_moves(n)

Arguments

Value

Named list of integer vectors, each a permutation of 1:(6*n^2) read as new[i] <- state[perm[i]]

See Also

cube_group, cube_nnn

Examples

m <- cube_moves(3)
names(m)

# the twelve face turns agree with the hand-written 3x3x3 table
identical(m[["R"]], cube_moves(3)[["R"]])

# a 4x4x4 has two inner layers per axis
names(cube_moves(4))

Description

The 3x3x3 is one member of a family, and the family is easier to describe than any single member of it. A move is an axis, a layer along that axis and a quarter turn; that vocabulary covers every cube, and what changes from one size to the next is only how many layers there are.

Details

On a 3x3x3 the three layers of an axis are the two faces and the slice between them — L, M, R going along x — so the slice turns come out of the same rule as the face turns rather than being added separately. On a 4x4x4 there are two inner layers per axis, and on a cube of side $n$ there are $n-2$.

Stickers

A state is an integer vector of length $6n^2$, one entry per sticker, numbered face by face in the order U R F D L B and within a face left to right, top to bottom as seen from outside. For $n = 3$ this is exactly the layout cube_nnn describes, and cube_group(3) agrees with cube_group move for move on the twelve face turns.

The alphabet

Three axes, $n$ layers, two directions: $6n$ moves. Half turns are not in it — U2 is the word "U U". This is the quarter-turn metric, and the choice matters because it is what a shortest path is counted in: the 3x3x3 face group has diameter 20 counting half turns as one move and 26 counting them as two.

Outer layers keep the letters the literature uses. The 3x3x3 slices are M, E and S, in their usual senses. Inner layers of larger cubes have no standard letter and are written axis-and-index, so "1x" is layer 1 along x.

What "solved" means

Once slices are in the alphabet the centres move, and a cube turned bodily in space is solved without its stickers being back where they started. cube_is_colour_solved is the test that allows for this; comparing against cube_identity is the stricter one that does not.

See Also

cube_group, cube_moves, cube_nnn for the 3x3x3 in particular

Description

One row per orbit: what kind of piece it holds, how many pieces are in it, and the depths and mirror sign that name it. See cube_orbits_family for what an orbit is and why it matters.

Usage

cube_orbits(n)

Arguments

Value

A data.frame with one row per orbit and columns orbit (index), label, kind ("corner", "edge" or "centre"), stickers_per_piece, n_pieces, depth_a, depth_b and chirality (-1, 0 or 1; non-zero only for one of a mirror pair).

See Also

cube_pieces, cube_progress

Examples

cube_orbits(3)   # corners, edges, fixed centres
cube_orbits(4)   # centres now move, edges are wings
cube_orbits(6)   # a mirror pair of centre orbits, labelled + and -

Description

"Corners and edges" is a sentence about a 3x3x3. A 4x4x4 has no edges in that sense — what looks like one is two wings that never swap — and its centres move. So the vocabulary has to come from the geometry, and these functions derive it rather than tabulating it.

Pieces

A piece is a cubie: a position carrying one sticker per face it touches, and how many faces it touches is the whole classification. Three stickers is a corner, and there are always eight of them whatever the size. Two is an edge piece — the twelve edges of a 3x3x3, splitting into wings on larger cubes. One is a centre, fixed on an odd cube only at the middle of each face.

Orbits

Two pieces are in the same orbit when some sequence of moves takes one to the other, and the point of an orbit is what it forbids: no word, however long, moves a piece out of its own. A method may therefore treat each orbit separately, which is most of what solving a large cube consists of.

Orbits are computed by walking the cube move by move from one piece and collecting everywhere it can go, so they are orbits by definition rather than by a rule that might be wrong. The labels only name what the walk found. A label reads f3:0,0,0 for the corners, f2:0,0,k for an edge orbit and f1:0,j,k for a centre orbit, where the numbers are each coordinate's distance to the nearer end of its range, sorted.

Where a class of centres holds two orbits that are mirror images of each other, the labels carry a trailing + or -. This happens on some sizes and not others — a 6x6x6 splits f1:0,1,2 and a 5x5x5 does not — which is why the orbits are walked rather than guessed.

Every orbit holds 24 pieces except three cases: the 8 corners, and on an odd cube the 6 fixed centres and 12 middle edges, all of which sit on a symmetry axis.

See Also

cube_orbits, cube_pieces, cube_progress, cube_group

Description

The second stage of reduction, after the centres are built: bring the pieces of each cube edge together so the cube can be finished as a 3x3x3. This is the generic form of pair_edges() in src/cube_edges.h.

Usage

cube_pair_edges(
  state,
  n = NULL,
  depth = 3L,
  max_rounds = 40L,
  keep_centres = TRUE
)

Arguments

Value

A list with state (the cube after the stage), path (the moves applied, as a character vector), whole (how many of the twelve edges ended whole), rounds and solved.

How it works

Try every algorithm under every setup word, take whatever pairs the most, repeat. The setup words are outer turns only — they carry an edge whole (measured; see cube_edge_map_family), so they can reposition the cube without ever undoing work. The algorithms are the six of cube_edge_algs. A round that cannot improve ends the stage.

A candidate is rejected outright if it disturbs the centres, so the stage can never spend what the centre stage built. That check is what keep_centres controls; turning it off is for diagnosis, not solving.

On the setup pool

The reference widened its pool to every composition of up to three outer turns, having measured five positions that stalled with anything shorter. depth is that number. Three gives 1885 words and is the default; two gives 157 and is enough to watch the stage work but not to finish reliably.

See Also

cube_edge_algs, cube_edge_counts, cube_build_lslice

Examples

set.seed(1)
s <- generate_state(group = cube_group(5), n_moves = 20)
r <- cube_pair_edges(s, depth = 2, max_rounds = 5)
r$whole

Description

Which stickers belong to which physical piece, in the form the piece encoding needs. Built from cube_pieces rather than written out here: which three stickers make a corner is a fact about the cube, and one measured table beats a transcribed one.

Usage

cube_piece_layout(group)

Arguments

Value

A list describing the layout: slots (integer matrix, one row per piece, its sticker positions padded with 0), n_piece, width (slots per piece), home (which piece each sticker belongs to) and turn (which of its slots each sticker is)

What it is for

A cube state is a permutation of sticker positions, and handing that to a network as 54 numbers makes it discover for itself that positions 1, 37 and 48 always travel together. They do so because they are one corner. The encoding below says that outright, which is the representation DeepCubeA uses: for every piece, which slot it currently occupies and how it is turned.

Centres

Centres are dropped only when no move disturbs them. Under face turns alone they never move, so on a 3x3x3 restricted to U/R/F/D/L/B they carry no information and are left out, giving DeepCubeA's 20 pieces. Add the slice moves M, E or S and the centres do permute — each slice moves four of them — so there they are kept and the layout has all 26. The decision is taken by applying the group's own moves and looking, not from the move names.

See Also

cube_adi_model, cube_pieces

Examples

g <- cube_group(3, moves = c("U", "U'", "R", "R'", "F", "F'",
                             "D", "D'", "L", "L'", "B", "B'"))
lay <- cube_piece_layout(g)
lay$n_piece   # 20: centres are fixed under face turns, so they are dropped

Description

One row per piece: where it sits, which orbit it belongs to, and which stickers of the state vector it carries.

Usage

cube_pieces(n)

Arguments

Value

A data.frame with one row per piece and columns piece, x, y, z, orbit, label, n_stickers and stickers — the last a comma-separated list of 1-based sticker indices.

See Also

cube_orbits, cube_progress

Examples

p <- cube_pieces(3)
nrow(p)                       # 26: 8 corners, 12 edges, 6 centres
head(p[p$n_stickers == 3, ])  # the corners

Description

The blunt summary of cube_progress: how many pieces are home out of how many there are.

Usage

cube_pieces_home(state)

Arguments

Value

A named integer vector with elements home and total.

See Also

cube_progress

Examples

cube_pieces_home(cube_identity(4))   # all of them

Description

Every stage of a solving method is "search until some predicate holds", so these predicates are the definitions of the stages. Reported together because what matters is usually which of them changed.

Usage

cube_predicates(state)

Arguments

Value

Named logical vector: cross_solved, slot_1 to slot_4, f2l_solved, oll_solved, first_layer_solved, ll_cross_oriented, ll_edges_placed, ll_corners_placed, cube_solved

See Also

cube_read_state, cube_solve_cfop

Examples

cube_predicates(cube_identity(3))   # all TRUE

Description

A measure of progress that works at any size. One number for a whole cube says too little — the orbits are solved at different times, and a method that has finished the centres and not the wings is in a quite different position from one that has done neither.

Usage

cube_progress(state)

Arguments

Details

A piece counts as home when every sticker in its slot shows the colour that slot has on a solved cube. That is a statement about colours rather than about sticker numbers, so a cube solved relative to its centres counts as solved — which is what a real cube looks like, and what the blindfold methods mean by the word.

The size is read from the state: a vector of 96 entries is a 4x4x4 and there is nothing else it could be.

Value

A data.frame with one row per orbit and columns orbit, label, kind, solved, total and fraction.

See Also

cube_orbits, cube_pieces_home

Examples

set.seed(42)
s <- generate_state(group = cube_group(4), n_moves = 30)
cube_progress(s)

Description

A cube state is 54 stickers, but a cuber sees 8 corners and 12 edges, each in some slot and turned some way. This is that reading, and it is what every stage predicate is built on: cp[i] is which corner sits in slot i, co[i] how far it is twisted, and likewise ep/ eo for edges. All indices are 0-based, as the C++ layer has them.

Usage

cube_read_state(state)

Arguments

Details

On a solved cube every cp/ep is its own index and every co/eo is zero.

Value

List with components cp, co (length 8) and ep, eo (length 12)

See Also

cube_predicates, cube_apply_word

Examples

cube_read_state(cube_identity(3))

Description

cube_reduce_cpp builds its first centre on one face and works from there. Which face that is was written into the pipeline as L; this runs it once per face and keeps the shortest reduction that actually reduces.

Usage

cube_reduce_best(state, faces = 0:5, verify = TRUE)

Arguments

Value

The result of cube_reduce_cpp for the best face, with two components added: face, the face it started from, and tried, a data.frame of every face with columns face, found, n_moves and verified. If no face reduces the cube, the result of the first face tried is returned with found left as it came.

Why the face matters

The method does not search for a short reduction, it follows a schedule — a centre, the layer beside it, the rest shot down from the top, then the edges — and the schedule runs whatever the cube arrived like. So the cost is decided by how the scramble happens to sit relative to the face the schedule starts on, and that is a property of the pairing, not of the cube.

Measured over 200 scrambles of depth 2 to 20, six faces each, every path verified by replaying it (inst/examples/ carries the survey):

• the default face is the best of the six on 22% of cubes;

• the median cube reduces 26% shorter by picking the best face, and 30038 moves over the whole set become 19202 — 64% of the default;

• no face wins often enough to be a better default: U leads at 53 of 200 and L, the old default, still wins 28. The gain is in trying them.

The saving holds at every depth measured, from 94% at depth 2 down to about 18% at depth 20, where the default already costs some 190 moves.

What it costs

Six reductions instead of one: about 0.32 seconds against 0.053 on the machine the survey ran on. Nothing is shared between the six — each starts from the state as given.

See Also

cube_reduce_cpp, cube_solve4, cube_is_reduced

Examples

set.seed(42)
s <- generate_state(group = cube_group(4), n_moves = 12)

res <- cube_reduce_best(s)
res$face
res$tried
length(res$path) <= length(cube_reduce_cpp(s)$path)

Description

Builds the centres, then pairs the wings with the algorithms speedcubers use – the setup-and-pair method, including the last-pair case and the OLL parity. The algorithms are listed in edge_algs() in src/cube_edges.h; nothing here searches for a move, it chooses among measured ones.

Arguments

Details

What it does not have is a fixed order. Each round takes whichever (setup, algorithm) pair leaves the most wings paired, which is where a greedy method can reach a position none of its algorithms improve. The script inst/examples/diag_pair_edges_stall.R measures how often that happens and what shape the position has.

Value

A list with found, path, stages, states (the cube after each stage) and failure – the reason it stopped, empty when it did not.

See Also

cube_solve4, which runs this and then finishes the 3x3x3 it leaves behind.

Description

The Kaggle Santa 2023 puzzles name a cube's moves f0, r1, -d2 and so on: a letter for the axis, an index for the layer, and a leading minus for the inverse. That is the same alphabet cube_moves builds — one quarter turn of one layer, $6n$ of them, half turns excluded — written differently, so the two are interchangeable once the correspondence is pinned down.

What differs

Two things, and neither can be guessed from the names.

The faces are numbered in a different order. Santa's 0..5 are our U, F, R, B, L, D; ours are U R F D L B. Inside a face the two layouts agree exactly — row by row, left to right, seen from outside — so the relabelling moves whole faces and never disturbs a face's interior.

The senses do not line up letter for letter. f3 is ⁠B'⁠ rather than B, d3 is ⁠U'⁠, d1 is ⁠1y'⁠. Written in axes and layers instead the irregularity disappears, which is why the correspondence is defined that way here:

A leading - inverts, which is 1 turn against 3.

Which correspondence

Sixteen relabellings satisfy all $6n$ equations, because a cube may be held sixteen ways that leave this alphabet looking like itself — four turns about the vertical, a choice of which pole is up, and a mirror. They are the same correspondence seen from different angles, not a genuine ambiguity, and the one used here is the one that keeps f0 as F and r0 as R.

States

A Santa state is $6n^2$ colours 0..5 in their face order; ours is $6n^2$ sticker numbers. cube_santa_state and cube_santa_state_out carry a state across, and cube_santa_perm carries the relabelling itself.

See Also

cube_santa_moves, cube_santa_state, cube_moves, cube_nnn

Description

The same group cube_group builds, with its moves named the way Santa 2023 names them. Solvers and searches work on it unchanged; only the names in the paths they return differ.

Usage

cube_santa_group(n)

Arguments

Value

An external pointer to the group, as cube_group returns

See Also

cube_santa, cube_group

Examples

g <- cube_santa_group(3)
group_apply(g, cube_identity(3), c("f0", "-d2"))

Description

The $6n$ move names Santa 2023 uses for a cube of side $n$, in the order its puzzle files list them: f0, -f0, f1 and so on through f, r and d.

Usage

cube_santa_move_names(n)

Arguments

Value

Character vector of length $6n$

See Also

cube_santa, cube_santa_moves

Examples

cube_santa_move_names(2)
cube_santa_move_names(4)

Description

cube_santa_moves names, for each Santa move, the package move that does the same thing; cube_moves_santa is its inverse.

Usage

cube_santa_moves(n)

cube_moves_santa(n)

Arguments

Details

The map is not letter for letter — f3 is ⁠B'⁠ on a 4x4x4, and d3 is ⁠U'⁠ — so it is derived from the geometry each time rather than tabulated. See cube_santa for why.

Value

Named character vector: names are the source notation, values the target one

See Also

cube_santa, cube_santa_perm

Examples

m <- cube_santa_moves(4)
m[c("f0", "f3", "d3", "d1")]

# and back again
cube_moves_santa(4)[c("F", "B'", "U'")]

Description

A Santa path is its moves joined by dots, as the submission files write them. cube_santa_path turns one into a character vector of package moves, and cube_santa_path_out turns package moves back into a Santa path.

Usage

cube_santa_path(path, n)

cube_santa_path_out(path, n)

Arguments

Details

Half turns have no name in either alphabet — both count in quarter turns — so a package move written U2 becomes two Santa moves.

Value

cube_santa_path returns a character vector of package moves; cube_santa_path_out returns one dot-separated string.

See Also

cube_santa, cube_santa_moves

Examples

cube_santa_path("f0.-d3.r1", n = 4)
cube_santa_path_out(c("F", "U", "2x"), n = 4)

Description

The permutation carrying a Santa 2023 sticker position to the package's own. Santa numbers the faces U F R B L D and we number them U R F D L B; within a face the two agree, so this permutation moves whole faces and nothing else.

Usage

cube_santa_perm(n, inverse = FALSE)

Arguments

Value

Integer vector of length $6n^2$

See Also

cube_santa, cube_santa_state

Examples

p <- cube_santa_perm(3)
length(p)

# applying it twice with the inverse gets back where it started
identical(cube_santa_perm(3, inverse = TRUE)[p], seq_len(54L))

Description

cube_santa_state turns a Santa state — the colours 0..5, or the letters a puzzle file writes them as — into a package state. cube_santa_state_out goes back the other way.

Usage

cube_santa_state(state, n = NULL)

cube_santa_state_out(state, n = NULL)

Arguments

Details

Santa writes a state in one of two ways, and both are read here. Most of its cube puzzles give a colour per sticker — 0..5, or the letters A to F — which is what cube_is_colour_solved and the solvers compare. Some give a distinct number per sticker instead, 0 to $6n^2 - 1$, which is a permutation and carries strictly more information: it says which of four identically coloured centres is which.

Both forms are relabelled the same way, because the relabelling acts on positions. Colours are additionally renumbered, since a colour is a face number and the two conventions order their faces differently; distinct sticker numbers are renumbered too, into the package's 1..6n^2.

Value

Integer vector of length $6n^2$: colours 0..5 numbered by the receiving convention's face order, or sticker numbers, matching whichever form was given. Package sticker numbers are 1-based and Santa's are 0-based.

See Also

cube_santa, cube_santa_perm

Examples

# a solved Santa 3x3x3 is nine of each colour in face order
s <- rep(0:5, each = 9L)
cube_santa_state(s)

# and back
identical(cube_santa_state_out(cube_santa_state(s)), s)

# the permutation form: Santa's solved state is 0..53, ours is 1..54
identical(cube_santa_state(0:53), seq_len(54L))

Description

The twelve centre cells of the layer lying against one face: that face's own four, together with the column each of the four faces around it presents to it. This is what step 2 of the reduction builds and what step 3 must not disturb.

Arguments

Value

A data.frame of twelve rows with columns face and slot.

Derived from the slice table

src/cube_centres.h used to write two of these out by hand — one for L, which step 2 builds, and one for D, where the rotation puts it. Both are read off the measured slice map instead: the layer of a face is that face plus whatever the slice lying beside it carries, and which of the two slices on the axis is the near one is settled by turning a solved cube and seeing which leaves the layer whole.

The slots are numbered as centre_slots_of in the C++ numbers them, which is not the numbering cube_centre_structure uses — that one runs along the face-turn cycle. The two tables are not comparable cell by cell.

See Also

cube_reduce_cpp, cube_slice_map

Examples

# the layer beside L: all of L, and a column of each face around it
cube_slice_cells_cpp(4)

# every face has one, and each is twelve cells
vapply(0:5, function(f) nrow(cube_slice_cells_cpp(f)), integer(1))

Description

The generic form of the slice table that src/cube_centres.h writes out by hand for a 4x4x4: one row per centre sticker the turn moves, saying which (face, orbit, slot) it leaves and which it arrives at.

Usage

cube_slice_map(n, move, structure = NULL)

Arguments

Value

A data.frame with columns from_face, from_orbit, from_slot, to_face, to_orbit and to_slot, with no rows if the move leaves every centre alone.

See Also

cube_centre_structure, cube_centre_map_family

Examples

# a 4x4x4 slice moves eight centres, in one orbit
m <- cube_slice_map(4, "1x")
nrow(m)

# no slice ever mixes two orbits, at any size
m5 <- cube_slice_map(5, "1x")
all(m5$from_orbit == m5$to_orbit)

Description

The first stage of reduction. On a 3x3x3 a centre is one sticker and cannot move; from 4x4x4 up each face carries four centre pieces, all twenty-four in a single orbit, and they have to be gathered before the cube can be treated as a 3x3x3 at all.

Usage

cube_solve_centres(state)

Arguments

Details

The method is Stefan Pochmann's layer-by-layer centres — the same author as the M2 method in cube_solve_m2. One centre is built, turned to the left, and the layer beside it is filled; then that layer goes to the bottom and the remaining pieces are shot down from the top one at a time. Two things are computed rather than searched for: which move carries a given piece where, and how far to turn U first so the shot has something to fire.

Whatever the shooting cannot reach is finished by commutators — a swap between two faces, or a 3-cycle among three — with the cube turned to meet each one rather than a variant of each kept per orientation. A 4-cycle is not a separate case: it is a 3-cycle followed by a swap.

Value

List with components:

See Also

cube_group, generate_state, cube_is_colour_solved

Examples

set.seed(42)
s <- generate_state(group = cube_group(4), n_moves = 40)

res <- cube_solve_centres(s)
res$found
length(res$path)

Description

Cross, then the four first-two-layer pairs, then orient the last layer, then permute it. The cross and the pairs are searched for optimally; the last layer is looked up in the standard tables of 57 OLL and 21 PLL cases. That division is the method's own: the first half is intuitive and the second is memorised.

Usage

cube_solve_cfop(state, cross_depth = 8L, slot_depth = 11L)

Arguments

Details

Each stage is solved optimally on its own and the total is still around three times optimal, because a stage that is shortest in isolation usually leaves the next one worse off. That gap is the price of a method a person can hold in their head. Move counts are quarter turns, so they run larger than the counts quoted in speedcubing, which count a half turn as one.

Value

List with components:

See Also

cube_solve_lbl, cube_group, generate_state

Examples

set.seed(42)
s <- generate_state(group = cube_group(3), n_moves = 20)

res <- cube_solve_cfop(s)
res$found
length(res$path)
res$stages

Description

The method a beginner is taught: cross on D, the four bottom corners, the four middle edges, then the last layer in four steps — make the yellow cross, place its edges, place the corners, twist them. Each last-layer step is a small algorithm applied over and over with a U turn between, which is why the method is easy to learn and long to execute.

Usage

cube_solve_lbl(state, cross_depth = 8L, corner_depth = 9L, edge_depth = 11L)

Arguments

Details

It shares the cross and the last layer with cube_solve_cfop. The middle is where it is slower and simpler: the bottom layer is finished outright, and only then do the middle edges go in one at a time. Expect roughly twice the moves of CFOP.

Value

List with the same components as cube_solve_cfop: path, found, stages, states.

See Also

cube_solve_cfop, cube_group, generate_state

Examples

set.seed(42)
s <- generate_state(group = cube_group(3), n_moves = 20)

res <- cube_solve_lbl(s)
res$found
length(res$path)

Description

Old Pochmann's method with a cheaper edge step, and the usual next thing a blindfold solver learns. There an edge was placed by a whole PLL wrapped in setup moves; here the buffer is DF and the swap is M2, which is two moves. The corners are unchanged.

Usage

cube_solve_m2(state)

Arguments

Details

M2 is not a clean swap, and the method is arranged around that rather than avoiding it. It turns the middle slice a half turn, so it moves the centres and exchanges the UF/DB edge as well. Those two get their own algorithms; edges left facing the wrong way are set aside while the chain runs and turned afterwards in one orientation phase; and whether the parity fix is needed is decided by reading the edge permutation rather than by counting swaps, because a chain that breaks into a new cycle spends turns the tally does not see.

The cube comes back solved with the centres sometimes rotated among themselves — "solved relative to the centres", which is what the method means by solved and what a real cube looks like.

Expect roughly two thirds the moves of cube_solve_old_pochmann, with the saving all on the edges.

Value

List with the same components as cube_solve_cfop: path, found, stages, states.

See Also

cube_solve_old_pochmann, cube_solve_cfop, cube_solve_lbl, cube_group

Examples

set.seed(42)
s <- generate_state(group = cube_group(3), n_moves = 20)

res <- cube_solve_m2(s)
res$found
length(res$path)

Description

The blindfolded method, and it is built on a different principle from the other two. CFOP and layer by layer both work by looking: a stage ends when the cuber can see that it has. Old Pochmann never looks at the cube after the start, so it repeats one step whose shape is always the same — swap whatever is in the buffer with one chosen piece, disturbing nothing else. Follow it and the pieces come home in a chain.

Usage

cube_solve_old_pochmann(state)

Arguments

Details

Nothing here is searched. Each piece is placed by a conjugate: setup moves that bring the target where the algorithm can reach it, one memorised algorithm, then the setup moves undone. The algorithms are ordinary PLLs, because "swap two edges and two corners" is exactly what a T-perm does, and the second swap is not incidental: a single swap is an odd permutation and the cube group has none. Those extra swaps cancel in pairs, and when their count is odd one is left over — that is the parity step, between the edges and the corners.

Expect around twice the moves of layer by layer. The cost of never looking is that no move ever does two things at once.

Value

List with the same components as cube_solve_cfop: path, found, stages, states. Each stage's detail names the target sticker by its standard letter and the algorithm used.

See Also

cube_solve_cfop, cube_solve_lbl, cube_group, generate_state

Examples

set.seed(42)
s <- generate_state(group = cube_group(3), n_moves = 20)

res <- cube_solve_old_pochmann(s)
res$found
length(res$path)

Description

Reduction is the standard way to solve an even cube: build the centres so each face acts as one, pair the edges so each acts as one, and the cube is then a 3x3x3 with fat pieces — finished by cube_solve_cfop.

Usage

cube_solve4(
  state,
  method = c("cfop", "kociemba", "lbl", "m2", "pochmann"),
  orientations = 1L,
  start_face = c("full", "reduction", "fixed")
)

Arguments

Details

Two things happen on a 4x4x4 that cannot happen on a 3x3x3, and both are handled here. The centres and edge pairs are not fixed relative to one another, so the first two stages are searches over the cube's own geometry rather than table lookups. And reduction can leave the last layer in a state no 3x3x3 reaches — OLL and PLL parity — which the 3x3x3 tables have no entry for; those are repaired with algorithms that turn inner layers, before the cube is handed on.

Expect roughly 300 quarter turns. The method is layer by layer throughout and makes no attempt at brevity; a search-based solver reaches the same cube in a fraction of the moves and a great deal more time.

Value

List with components:

What the reduction costs, and why

The length is a property of the method rather than of the position, and the clearest case measured is this. A cube eight moves from solved — scrambled by R' D U U' 2z B 1x' 1z' — was reduced in 204 moves. Walking the inverse scramble back shows a reduced state four moves away: the fourth move of the way home already satisfies cube_is_reduced. The method built one in two hundred and four while one lay in four.

It is not a defect of the implementation. The reduction does not look for the NEAREST reduced state; it builds its own by a fixed schedule — one centre, then the layer beside it, then the top slice emptied, then the edge pairs — and every stage runs whatever the cube arrived like. Following one such solution move by move, 74% of the moves changed neither the count of centres home nor the count of edges paired. The edge stage spent 107 moves pairing twelve edges, nine apiece, with the centres flickering between four and eight all the way: take them apart, pair an edge, put them back.

That is also why no cheap test predicts the price. The sum of missing centres, their arrangement over the faces, and the number of unpaired edges were each measured against the length over 420 cubes, and none separates a cheap cube from an expensive one — because there is little to separate. Only the threshold shows: while a cube is still reduced the stage does almost nothing (three to eight moves), and once it is not, the schedule runs in full at a price that barely depends on how far from solved it is.

Searching for a nearby reduced state instead does not rescue this. Reduced is a weak condition and countless states satisfy it, but iterative deepening still walks the whole tree to each depth before the next, so the many goals buy nothing — measured, a fourteen-move scramble did not finish inside six minutes at depth six. Using the gap would want a prune table over the distance to reduced, which is what cube_kociemba has for the 3x3x3 and this does not.

What does help is choosing where the schedule starts. If the price turns on how the scramble sits relative to the face the first centre is built on, then that face is worth picking rather than fixing, and start_face below is how it is picked. Measured over 200 scrambles, the face that had been written into the pipeline is the best of the six on 22% of cubes; the reduction stage alone falls to 64% of its length when all six are tried.

Picking by the reduction is not the same as picking by the answer, though, and the difference is not small. A short reduction can leave the cube in a parity a longer one avoids, and the fifty moves that costs outweigh what it saved. Over 40 scrambles the two criteria chose differently on 48% of cubes, the reduction criterion losing 70 moves on average and 152 at worst — and on four of the forty it produced a solution LONGER than the fixed face would have. Choosing on the finished solution cannot do that, since the fixed face is one of the six it compares.

orientations below is the same effect reached from the other side: the same cube held differently reduces in anything from 139 moves to 312, and that range is the view rather than the position.

See Also

cube_solve_centres, cube_solve_cfop, cube_group

Examples

set.seed(42)
s <- generate_state(group = cube_group(4), n_moves = 40)

res <- cube_solve4(s)
res$found
length(res$path)

Description

Phase 3 of the reduction is usually cheap when it succeeds and expensive when it fails, and the two are told apart only afterwards. So the leash is a ladder rather than a single length: every orientation is tried at a small budget before any is tried at a large one. See budget_steps.

Usage

cube_solve4_cascade(
  state,
  node_budget = 2e+05,
  prep_budget = 5e+06,
  orientations = c("", "1y", "1x", "1z"),
  max_orientations = 4L,
  phase2_solutions = 4L,
  max_candidates = NA_integer_,
  shuffle_candidates = FALSE,
  workers = 1L,
  budget_steps = c(0.1, 0.3),
  exact_centres = TRUE,
  verbose = FALSE,
  progress_every = 0
)

Arguments

Details

When no orientation reduces the cube at any rung, cube_solve4 finishes the job. That solver always succeeds and its solutions are long – 186 to 444 moves on six random cubes – so it is the floor rather than the goal.

The fallback is not a failure mode to be minimised away. A reduction that does not finish inside its budget has not proved the cube unreachable – the outcome is exhausted, which means the budget ran out, and phase 3's true distance is simply further than the leash allowed. What the cascade buys is a bounded wait: an answer of some length always, rather than an optimal one sometimes.

Value

A list with path (the moves), method ("reduce", "solve4", "already-solved" or "unsolved"), solved (the path was replayed and checked, not assumed), orientation (the rotation that worked, empty for none), candidate (which of that orientation's phase-2 solutions it was, as "1y#4" – the rotation alone does not say, and with several solutions per orientation the difference is most of the time a slow cube spends), n_moves, seconds, attempts, and ops.

ops is a data.frame with one row per operation performed, in the order performed: op ("phase 1", "phase 2", "phase 3", "tail solve4", "verify" and so on), secs, detail (the orientation, and for phase 3 the rung), nodes and outcome. Unlike attempts it covers the attempts that failed as well as the one that worked, which is where most of a slow cube's seconds are: its rows sum to seconds up to a final "unaccounted" row, so nothing is left implicit.

Examples

## Not run: 
set.seed(8)
mv <- cube_moves(4); names(mv) <- cube_move_names(4)
s <- cube_identity(4)
for (m in sample(cube_move_names(4), 6, replace = TRUE)) s <- s[mv[[m]]]
r <- cube_solve4_cascade(s)
r$method

## End(Not run)

Description

A wide turn is a face together with the inner layer behind it, turned as one slab — Rw, Uw, Dw in the notation the published edge algorithms are written in. This gives the pair of package moves that make one up, at any size.

Usage

cube_wide_turn(n, face, prime = FALSE)

Arguments

Value

A character vector of package moves.

Why this is measured

src/cube_edges.h carries the expansions as constants: Dw -> D 1y\', Uw -> U 2y, Rw -> R 2x. Two things in those are 4x4x4 facts — which numbered slice lies behind a face, and nothing else. Measured across n = 4, 5, 6: a slice k<axis> turns layer k, and the faces sit at layers 0 and n - 1, so the layer behind a face is 1 for D, L, B and n - 2 for U, R, F. At n = 4 that returns the three constants above.

The direction is not free either, and edge-wholeness cannot decide it: both directions leave 8 edges whole, and both have order 4, because a face and a slice on the same axis commute. What separates them is whether the slab turns as one rigid rotation. Measured by asking whether every piece the composite moves undergoes the same rotation in the plane perpendicular to the axis: U, R, F take the slice straight and D, L, B take it inverted — uniform at n = 4 and n = 5 alike, and agreeing with the three constants.

See Also

cube_edge_algs, cube_moves

Examples

cube_wide_turn(4, "R")        # R 2x  -- the Rw of the sources
cube_wide_turn(5, "R")        # R 3x  -- the same turn on a bigger cube
cube_wide_turn(4, "D")        # D 1y\' -- low faces take the slice inverted

Description

How many times a word must be repeated before the cube returns to where it started. A quarter turn has order 4 and a half turn order 2; a word that is not what its name says will have some other order, which is what makes this a check on the alphabet rather than a curiosity.

Usage

cube_word_order(word, max_order = 1260L)

Arguments

Value

Integer, the order, or -1 if none was found within max_order

See Also

cube_apply_word

Examples

cube_word_order("R")        # 4
cube_word_order("R2")       # 2
cube_word_order("R U R' U'")  # 6

Description

Shortens an existing path by looking for cycles that leave it and rejoin it further along. A cycle here is a combo word (say "1231") applied round and round until the state returns to where the cycle started – the same construction find_path_iterative searches with. If some state along that loop also occurs later in the path, the stretch between the two meeting points can be replaced by the stretch of the loop, and whenever the loop covers it in fewer operations the path gets shorter.

Usage

cycle_shortcut(
  path,
  start_state,
  k = NULL,
  n_points = 20L,
  moves = NULL,
  group = NULL,
  combo_length = 20L,
  n_samples = 200L,
  n_top = 5L,
  sort_by = c("longest", "most_unique"),
  max_cycle_len = 20000L,
  n_threads = NULL,
  verbose = FALSE
)