Package {cayleyR}

Type:	Package
Title:	Cayley Graph Analysis for Permutation Puzzles
Version:	0.3.0
Description:	Analyzes Cayley graphs of permutation puzzles. Any puzzle whose moves permute a fixed set of positions can be declared as a permutation group, and the same tools then work on it: cycle detection, state space exploration and path search. Two puzzles are built in: TopSpin and Rubik's cubes of any size. The 3x3x3 is solved by four human methods and by a two-phase search after Herbert Kociemba; the 4x4x4 is solved by reduction. The Iterative Cycle Intersection (ICI) method is described in Yuri Baramykov (2026) <doi:10.48550/arXiv.2607.13219>.
License:	MIT + file LICENSE
Encoding:	UTF-8
RoxygenNote:	7.3.3
Imports:	Rcpp, utils
LinkingTo:	Rcpp
Suggests:	testthat (≥ 3.0.0), ggmlR, parallel, data.table, jsonlite, knitr, rmarkdown
Config/testthat/edition:	3
VignetteBuilder:	knitr
URL:	https://github.com/Zabis13/cayleyR, https://arxiv.org/abs/2607.13219
BugReports:	https://github.com/Zabis13/cayleyR/issues
NeedsCompilation:	yes
Packaged:	2026-10-19 10:59:05 UTC; yuri
Author:	Yuri Baramykov [aut, cre], Lucas Garron [ctb, cph] (twips search machinery in src/kociemba_core.h, src/kociemba4.h), cubing.js authors [cph] (twips, https://github.com/cubing/twips)
Maintainer:	Yuri Baramykov <lbsbmsu@mail.ru>
Repository:	CRAN
Date/Publication:	2026-10-19 12:20:08 UTC

cayleyR: Cayley Graph Analysis for Permutation Puzzles

Description

Implements algorithms for analyzing Cayley graphs of permutation groups, with a focus on the TopSpin puzzle and similar combinatorial problems. Provides C++ implementations of core operations via Rcpp, cycle detection, state space exploration, bidirectional BFS pathfinding, and finding optimal operation sequences in permutation groups generated by shift and reverse operations. Optional GPU acceleration via ggmlR Vulkan backend for batch distance calculations and parallel state transformations.

Details

Main Features

• Basic permutation operations (C++): cyclic left/right shifts, prefix reversal

• Cycle analysis: find cycles in Cayley graphs with detailed state information

• Sequence optimization: search for operation sequences with maximum cycle length

• Bidirectional BFS: find shortest paths between permutation states

• Iterative solver: find paths between arbitrary states via iterative cycle expansion

• Celestial coordinates: map LRX operation counts to spherical coordinates

• GPU acceleration (optional): Vulkan-based batch computations via ggmlR

• Fast processing: lightweight version for batch testing of combinations

Main Functions

Basic Operations (C++):

• shift_left() / shift_right() - Cyclic shifts with coordinate tracking

• shift_left_simple() / shift_right_simple() - Simple cyclic shifts (no coords)

• reverse_prefix() / reverse_prefix_simple() - Reverse first k elements

• apply_operations() - Apply sequence of operations

Analysis Tools:

• get_reachable_states() - Full cycle analysis with state tracking

• get_reachable_states_light() - Lightweight cycle detection

• find_best_random_combinations() - Find best random sequences

• analyze_top_combinations() - Analyze top operation sequences

Pathfinding:

• bidirectional_bfs() - Bidirectional BFS shortest path

• find_path_iterative() - Iterative path solver

GPU (optional, requires ggmlR):

• cayley_gpu_available() / cayley_gpu_init() / cayley_gpu_status() - GPU management

• calculate_differences() with use_gpu = TRUE - Manhattan distance on GPU

• apply_operations_batch_gpu() - Batch operations via matrix multiplication

• manhattan_distance_matrix_gpu() - Pairwise distance matrix

Utilities:

• convert_digits() - Parse operation strings

• generate_state() / generate_unique_states_df() - Random state generation

• manhattan_distance() - Distance between states

• convert_LRX_to_celestial() - Map operations to celestial coordinates

Author(s)

Yuri Baramykov lbsbmsu@mail.ru

References

• TopSpin puzzle: https://www.jaapsch.net/puzzles/topspin.htm

• Cayley graphs: https://en.wikipedia.org/wiki/Cayley_graph

See Also

Useful links:

• https://github.com/Zabis13/cayleyR

• https://arxiv.org/abs/2607.13219

• Report bugs at https://github.com/Zabis13/cayleyR/issues

Single-batch GPU pairwise Manhattan distance

Description

Uses 3D tensors: repeat s1 along dim2, repeat s2 along dim1, then sub -> abs -> sum_rows. Result shape is (1, N1, N2) which gives the N1 x N2 distance matrix.

Usage

.manhattan_distance_matrix_gpu_batch(states1, states2)

Arguments

Value

Numeric matrix (N1 x N2)

Setup GPU backend (internal)

Description

Checks if GPU is available via cayley_gpu_available() and initializes if so.

Usage

.setup_gpu()

Value

Logical, TRUE if GPU is ready

Add State Keys to Data Frame

Description

Computes paste-based state keys for V-columns and adds a state_key column. If keys already exist, only computes for new rows.

Usage

add_state_keys(states_df, new_states, v_cols)

Arguments

Value

Data frame with state_key column

Analyze Top Operation Combinations

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)

Apply Sequence of Operations

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

Apply operations to batch of states on GPU

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)
}

Bidirectional BFS Shortest Path

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)

Breakpoint Distance Between Two States

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)

Build permutation matrix for a single operation

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)

Angular Distance Between Two Celestial Points

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)

Calculate Manhattan Distances for All States

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)

Calculate Manhattan Distances on GPU

Description

Computes Manhattan distance from a reference state to each row of a matrix using ggml Vulkan backend: sub -> abs -> sum_rows.

Usage

calculate_differences_gpu(start_state, states_matrix)

Arguments

Value

Numeric vector of Manhattan distances (length nrow)

Midpoint Between Two Celestial Coordinates

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

Full Breadth-First Search Over the Cayley Graph

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)

Check if GPU acceleration is available

Description

Checks whether ggmlR is installed and Vulkan GPU is present.

Usage

cayley_gpu_available()

Value

Logical

Examples

cayley_gpu_available()

Free GPU backend resources

Description

Free GPU backend resources

Usage

cayley_gpu_free()

Value

Invisible NULL

Initialize GPU backend

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()
}

Get GPU status information

Description

Get GPU status information

Usage

cayley_gpu_status()

Value

List with availability, device info, and backend status

Examples

cayley_gpu_status()

Cayley Graph Diameter and Maximally Distant State Pairs

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

Find Duplicate States Between Two Tables

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)

Compose permutation matrices for a sequence of operations

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)

Convert LRX Counts to Celestial Coordinates

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

Convert String to Integer Vector of Digits

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")

Convex Hull of a 3-D Point Cloud

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

Create Hash Index from State Keys

Description

Builds a hash environment mapping state_key strings to row indices for fast lookup.

Usage

create_hash_index(states_df)

Arguments

Value

Environment (hash table) mapping keys to integer vectors of row indices

Create a New State Store

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)

Autodidactic Iteration on a Permutation Puzzle

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

Batch Weighted A* With a Learned Heuristic

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

All Children of Each State

Description

Applies every move to every state. The result is one matrix of nrow(states) * n_moves children, laid out state-major so that row (i - 1) * n_moves + a is child a of state i. That is the layout the value network scores in a single pass, and the layout cube_adi_targets reads back.

Usage

cube_adi_children(group, states)

Arguments

Value

List with children (integer matrix, state-major) and solved (logical vector, whether each child is the identity)

One-Hot Encoding of States by Piece

Description

The piece encoding of cube_adi_model(encoding = "piece"), built here rather than in R because it runs on every batch of every iteration. The R version allocates a n x P x P*W array and fills it with a loop per piece, which on a batch of a few thousand costs more than the training step it feeds.

Usage

cube_adi_encode_pieces(states, first_slot, home, turn, n_piece, width)

Arguments

Details

Each of the P piece slots gets P * W bits, one per (piece, turning) pair, and exactly one of them is set: which piece is sitting in that slot, and which way round. The piece is read off the slot's first sticker, since every sticker of a slot comes from one piece.

Value

Numeric matrix n x (n_piece * n_piece * width)

Hash a Batch of States to Keys

Description

A search has to recognise a state it has already reached, and the obvious way to do that from R – paste(state, collapse = ",") per row – costs more than the network forward pass once the open list runs to hundreds of thousands of nodes. This does the same job in one pass over the matrix.

Usage

cube_adi_keys(states)

Arguments

Details

The keys are 64-bit FNV-1a hashes returned as doubles. A double carries 53 bits exactly, so the hash is folded down to 53 bits rather than truncated: the alternative is silently rounding two distinct hashes onto the same double. Collisions are still possible in principle – at 2^53 keys and a search of 10^6 nodes the chance is around 10^-4 – and the caller that cannot afford one has to compare the states themselves.

Value

Numeric vector of keys, one per row

Load a Trained ADI Network

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

Build the Value and Policy Networks

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

Save a Trained ADI Network

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

Random Scrambles From the Solved State

Description

Walks away from the identity by a uniformly random number of moves between 1 and max_depth, n times over. Uniform in depth is the sampling ADI asks for: it is what lets accuracy spread outward from the states near the goal without any weighting in the loss.

Usage

cube_adi_scramble(group, n, max_depth)

Arguments

Details

The walk never undoes its own last move. A move immediately followed by its inverse returns the state to where it was and would quietly make the scramble shorter than its label. Longer cycles are left alone – they are rarer, and ADI's targets do not depend on the label being exact anyway.

Value

List with states (n x state_len integer matrix) and depth (integer vector, the scramble length of each row)

Solve a Cube With a Trained Network

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

ADI Targets From Children Values

Description

The value target of a state is min_a (1 + v(child_a)) and its policy target is the move attaining that minimum. Value is cost-to-go, so the network learns a distance and the solved state is zero.

Usage

cube_adi_targets(child_values, child_solved, n_moves)

Arguments

Details

Solved children are what anchors the scheme. A child that is already solved contributes exactly 1 no matter what the network says about it, so states one move from the goal get an exact target from the first iteration onward, and deeper states inherit that accuracy through their neighbours as training goes on. This is why ADI needs no weighting by depth.

Value

List with value (numeric) and policy (integer, the 1-based index of the best move)

Train Value and Policy by Autodidactic Iteration

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

The Algorithm Tables

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)

Apply a Word of Moves to a Cube State

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)

Build the Layer Beside a Face, at Any Size

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)

Slice Turns That Reorient the Whole Cube

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

Count the Centre Pieces That Are Home

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)

Three-Cycles of Centres, One Per Orbit

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)

The Centres of a Cube of Any Size, Derived

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

Sticker Positions of the Six Centres

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())

Commutators That Carry Centres Off One Face and Spare Another

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)

Centre Stickers of an N x N x N Cube

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)])

Colours and Positions: the Two Ways to Write a Cube Down

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)))

The Published Edge-Pairing Algorithms, at Any Size

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

How Many Edges Are Whole

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

Where a Turn Sends Each Edge Piece

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

The Edges of a Cube of Any Size, Derived

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

Edge Pieces of an N x N x N Cube

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)

Empty the Top Face onto the Sides

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

Expand an Algorithm into the Package's Alphabet

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

Wide Turns and Whole-Cube Rotations

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)

The Group of an N x N x N Cube

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")

Solved State of an N x N x N Cube

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))

Test Whether Every Face of a Cube is a Single Colour

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))

Is a Cube Reduced?

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))

Solve a 3x3x3 by Two-Phase Search

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))

Solve a 4x4x4 by Four-Phase Search

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

Reduce a 4x4x4 by Four-Phase Search

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

What the Last 4x4x4 Reduction Did

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

Build the Kociemba Prune Tables

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()

What the Last Kociemba Solve Did

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()

A Single Layer Turn, by Axis and Layer

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"]])

The Layer Beside a Face, and What Leaves It Alone

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)

Move Names of an N x N x N Cube

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)

Move Table of an N x N x N Cube

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))

Cubes of Any Size

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

Orbits of an N x N x N Cube

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 -

Piece Orbits of a Cube of Any Size

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

Pair the Edges of a Cube of Any Size

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

The Piece Layout a Cube State Is Read Through

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

Pieces of an N x N x N Cube

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

Pieces Home on a Cube

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

Stage Predicates of a Cube State

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

How Much of Each Orbit Is Solved

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)

Read a Cube State as Pieces

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))

Reduce a 4x4x4, Trying Every Starting Face

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)

Reduce a 4x4x4 by the human method

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.

Usage

cube_reduce_cpp(state, target_face = 4L)

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.

The Santa 2023 Cube Notation

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

A Cube Group in Santa 2023 Notation

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"))

Santa 2023 Move Names for a Cube

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)

Translate Between Santa 2023 and Package Move Names

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'")]

Translate a Santa 2023 Solution Path

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)

Sticker Relabelling Between Santa 2023 and This Package

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))

Read and Write Santa 2023 Cube States

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))

The Layer Beside a Face, as the 4x4x4 Solver Sees It

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.

Usage

cube_slice_cells_cpp(face)

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))

Where a Slice Turn Sends Each Centre

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)

Solve a 4x4x4 Cube by Reduction

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)

Solve a 4x4x4 by reduction, falling back when the search does not pay off

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)

Solve the Centres of a 4x4x4 Cube

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)

Solve a 3x3x3 Cube by CFOP

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

Solve a 3x3x3 Cube Layer by Layer

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)

Solve a 3x3x3 Cube by M2

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)

Solve a 3x3x3 Cube by Old Pochmann

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)

Wide Turns of an N x N x N Cube

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

Order of a Word of Moves

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

Shorten a Path by Cutting Across Cycles

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
)

Arguments

Details

This complements short_path_bfs rather than replacing it. That one sweeps the BFS neighbourhood a few steps deep, so it finds cuts between nearby points; a cycle wanders hundreds of steps from where it started and reaches rejoin points BFS depth cannot see. Running one after the other is reasonable.

Points are processed one at a time, and a cut is applied the moment it is found: every later point is then searched against the already-shortened path. This is why the points are carried as states rather than as positions – a cut renumbers everything downstream of it, but a state is either still somewhere in the path or it is not. Points swallowed by an earlier cut are simply skipped.

Value

List with components:

See Also

short_path_bfs, human_algorithm_to, find_path_iterative

Examples

set.seed(1)
s <- generate_state(20, k = 4, n_moves = 300)
res <- human_algorithm_to(s, k = 4, simplify = FALSE)
cut <- cycle_shortcut(res$path, s, k = 4, n_points = 5)
cut$savings

Distance Methods for Bridge Selection

Description

The registry of methods find_path_iterative may use to score candidate states when picking bridges. Each method is a function f(states, target, k) returning one score per row of states; lower is better. The search takes the lowest-scoring candidate, breaking ties on the smaller step number.

Usage

cayley_distance_methods()

cayley_distance(method)

Arguments

Details

manhattan

Sum of absolute differences to the target. The default, and the only behaviour available before methods became pluggable.

breakpoints

Number of adjacency violations relative to the target – positions where consecutive values are not consecutive in the target's frame. Often a better guide than raw displacement.

human

How far the state is from being solved the way a person solves it: the number of tiles still missing from the sorted run. Scores against the identity 1:n and ignores target, so it applies only to searches heading for the sorted ring. Ties break on the gap phase 1 works to close. See find_best_match_human.

cube4_model

Moves still to play on a 4x4x4, read off a trained model rather than counted. The other methods score how far two states are as arrays, which on a cube says little about how far they are as cubes: two states one quarter turn apart can differ in most of their stickers. This one asks a model that was trained to predict exactly that number. Like human it scores against the solved cube and ignores target, so it belongs to searches heading for the solved state. See find_best_match_cube4_model.

Every method is a function of (states, target, k): a matrix with one candidate state per row, the state being approached, and the flipper width (used by human, ignored by the rest). It returns one score per row, lower being better, with NA marking a candidate it rejects. Those are the arguments of the returned method, not of the two functions here.

Value

cayley_distance_methods() returns the registered names; cayley_distance() returns the method itself, as a function.

See Also

find_path_iterative, human_phase1_rank

Examples

m <- rbind(c(1L, 2L, 3L, 4L), c(4L, 3L, 2L, 1L))
cayley_distance_methods()          # registered method names
cayley_distance("manhattan")(m, 1:4, 4)

Enclosing Hull Through Every Point

Description

Builds a closed triangulated surface whose vertices are all the given points, not just the ones on the convex boundary.

Usage

enclosing_hull_3d(pts, tol = 1e-09)

Arguments

Details

convex_hull_3d returns the smallest convex body containing the cloud, so any point strictly inside it is not a vertex of the result. When the point set is meant to be read as the corners of one figure, that is the wrong answer: some of the corners go missing. This function starts from the convex hull and then, for each interior point in turn, replaces the triangle whose plane it sits closest under with three triangles meeting at that point. The surface is dented inwards there, so the body stops being convex, but every supplied point ends up on it.

Because the surface is no longer convex, the volume is computed as the signed sum of tetrahedra over the oriented faces, which stays correct for any closed surface that does not intersect itself.

Value

A list with the same components as convex_hull_3d plus

See Also

convex_hull_3d

Examples

set.seed(1)
p <- rbind(as.matrix(expand.grid(c(0, 1), c(0, 1), c(0, 1))), c(0.5, 0.5, 0.5))
h <- enclosing_hull_3d(p)
length(h$vertices)   # 9: the interior point is a vertex too

Filter Middle States

Description

Removes the first and last steps from each combo within cycle data, keeping only middle states.

Usage

filter_middle_states(data, skip_first = 2, skip_last = 2)

Arguments

Value

Data frame with filtered states

Score Candidate States With a Trained 4x4x4 Model

Description

Distance is the model's own answer to "how many quarter turns from solved": it scores the 24 moves of a state and the smallest of them is taken as the state's value. The whole candidate set goes through in one call, because the model batches and a per-row call would cost far more than the scoring.

Usage

find_best_match_cube4_model(states, target, k)

Arguments

Details

Scoring is against the solved cube and target is ignored, the same arrangement find_best_match_human uses and for the same reason: the model was trained towards one particular state and cannot be asked about distance to an arbitrary one. Use it for searches heading for the solved cube; on a search heading elsewhere the numbers do not describe the pair being compared.

The value is a prediction, not a count. It is close enough to guide a choice between candidates – which is all bridge selection needs – but it carries no guarantee, and a search that needs an exact answer near the solved cube should get it from the group, not from here.

The model is read once and kept for the session. Set CUBE4_ARCHIVE to the directory holding model/model.pth; ggmlR must be installed.

Registered as distance method "cube4_model"; see distance_methods.

Value

Numeric vector of scores, one per row; lower is better

See Also

distance_methods, find_best_match_human

Score Candidate States the Way a Person Solves

Description

Distance is how much of the sorted run is still missing: n - run_length. Within a run length, ties break on the gap phase 1 works to close, so among states with an equal run the one closest to placing its next value scores lower.

Usage

find_best_match_human(states, target, k)

Arguments

Details

Scoring is against the identity 1:n and target is ignored. That is deliberate, not an oversight: run_length only means something when the goal is the sorted ring. Relabelling into an arbitrary target's frame was tried and performed worse – the side of a two-ended search that grows from an unstructured state ends up judged against a goal phase 1 cannot read. Use this method for searches heading for 1:n, as the tail search after phase 1 does.

Registered as distance method "human"; see distance_methods.

Scoring runs in C++ (human_distance_cpp); the whole candidate set is scored in one call.

Value

Numeric vector of scores, one per row; lower is better

See Also

distance_methods, human_phase1_rank

Find Best Match State

Description

Finds the state in a table that has the minimum Manhattan distance to a target state. If multiple states tie, selects the one with the smallest step number.

Usage

find_best_match_state(
  target_state,
  reachable_states,
  method = "manhattan",
  use_gpu = FALSE
)

Arguments

Value

Single-row data frame of the best matching state

Find Best Random Operation Sequences

Description

Generates random sequences of operations and evaluates their cycle lengths to find sequences that produce the best cycles in the Cayley graph. Uses C++ with OpenMP for parallel evaluation of combinations.

Usage

find_best_random_combinations(
  moves = NULL,
  combo_length,
  n_samples,
  n_top,
  start_state,
  k = NULL,
  group = NULL,
  sort_by = c("longest", "most_unique"),
  max_moves = 10000000L
)

Arguments

Value

Data frame with columns:

Examples

# Default: longest cycles
best <- find_best_random_combinations(
  moves = c("1", "2", "3"),
  combo_length = 10,
  n_samples = 50,
  n_top = 5,
  start_state = 1:10,
  k = 4
)

# Short cycles with many unique states
best2 <- find_best_random_combinations(
  moves = c("1", "2", "3"),
  combo_length = 10,
  n_samples = 50,
  n_top = 5,
  start_state = 1:10,
  k = 4,
  sort_by = c("shortest", "most_unique")
)

Find Closest State to Target Coordinates

Description

Searches a table of reachable states for the state whose celestial coordinates are closest to a target coordinate set.

Usage

find_closest_to_coords(reachable_states, target_coords, v_cols)

Arguments

Value

Single-row data frame of the closest state (with angular_distance column added)

Examples

# Typically used with output from get_reachable_states
# find_closest_to_coords(states_df, target_coords, paste0("V", 1:n))

Find a State in Reachable States Table

Description

Searches for a specific permutation state in a reachable states table and returns the first matching row with metadata.

Usage

find_combination_in_states(reachable_states_start, search_state)

Arguments

Value

Data frame row with state and metadata columns, or NULL if not found

Examples

df <- data.frame(V1 = c(1, 2), V2 = c(2, 1), operation = c("1", "2"),
                 step = c(1, 2), combo_number = c(1, 1))
find_combination_in_states(df, c(2, 1))

Find Path via BFS Highways

Description

Builds BFS highway trees from start and final states, finds the closest pair of hub states (one from each highway), then uses find_path_iterative to connect them. Assembles the full path: bfs(start -> hub_s) + iterative(hub_s -> hub_f) + inverted_bfs(final -> hub_f)

Usage

find_path_bfs(
  start_state,
  final_state,
  k = NULL,
  group = NULL,
  bfs_levels = 500L,
  bfs_n_hubs = 7L,
  bfs_n_random = 3L,
  highway_distance_method = "manhattan",
  iterative_distance_method = highway_distance_method,
  verbose = TRUE,
  ...
)

Arguments

Value

List with path, found, cycles, bfs_info

Iterative Path Finder Between Permutation States

Description

Finds a path between two permutation states using iterative cycle expansion. Generates random operation sequences, analyzes their cycles, and looks for intersections between forward (from start) and backward (from final) state sets. Uses bridge states to progressively narrow the search space.

Usage

find_path_iterative(
  start_state,
  final_state,
  k = NULL,
  moves = NULL,
  group = NULL,
  combo_length = 20,
  n_samples = 200,
  n_top = 10,
  max_iterations = 10,
  potc = 1,
  ptr = 10,
  opd = FALSE,
  reuse_combos = FALSE,
  keep_states = FALSE,
  one_sided = FALSE,
  distance_method = "manhattan",
  sort_by = c("longest", "most_unique"),
  max_scored = NULL,
  verbose = TRUE
)

Arguments

Details

Uses a compact C++ StateStore backend for O(1) incremental hash-indexed state storage, eliminating quadratic memory growth from repeated rbind.

Value

List containing:

Examples

# Small example
set.seed(42)
start <- 1:6
final <- c(3L, 1L, 2L, 6L, 4L, 5L)
# result <- find_path_iterative(start, final, k = 3, max_iterations = 5)

Generate Reachable Random State

Description

Generates a random state by walking away from the identity with random moves. The walk stays inside the group, so the result is always reachable from where it started — which a random permutation of 1:n would not be. On the cube that distinction is the whole point: of the 54! arrangements of 54 stickers only about 4.3 \times 10^{19} are positions a cube can actually reach.

Usage

generate_state(
  n = NULL,
  k = NULL,
  n_moves = 25L,
  moves = NULL,
  group = NULL,
  max_attempts = 100L
)

Arguments

Details

Given a group, moves are drawn from that group's alphabet. Without one the arguments describe TopSpin, as they always have, and moves names its operations "1"/"2"/"3".

Value

Integer vector representing a reachable permutation state

See Also

cube_group, for the cube's own moves and also reports the moves it used

Examples

set.seed(42)
generate_state(10, k = 4)
generate_state(10, k = 4, n_moves = 100)

# in an arbitrary group: n comes from the group
g <- cube_group(3)
s <- generate_state(group = g, n_moves = 20)
length(s)

# the centres of a real cube never move, and this state is a real one
all(s[c(5, 14, 23, 32, 41, 50)] == c(5, 14, 23, 32, 41, 50))

Generate Data Frame of Unique Random States

Description

Generates a data frame with unique random permutation states.

Usage

generate_unique_states_df(n, n_rows)

Arguments

Value

Data frame with n_rows rows and columns V1, V2, ..., Vn

Examples

set.seed(42)
df <- generate_unique_states_df(5, 10)
head(df)

Random Walks From the Solved State, With the Moves They Took

Description

Walks away from the identity by random moves and reports the word it walked, which is what separates this from generate_state. That function hands back a state and forgets the route; this one hands back the route as well, and the route is a way home — invert_path of it solves the state.

Usage

generate_walk(
  group,
  n = 1L,
  n_moves = 10L,
  exact = TRUE,
  no_undo = TRUE,
  pivot = FALSE,
  k_min = 2L,
  no_cancel = FALSE
)

Arguments

Details

That matters wherever a solver is measured rather than merely run. Asking where an estimator ranked the helping move, or at which step a search dropped the trail, needs a state whose answer is known in advance, and the only cheap way to know one is to have walked there.

Two switches, because generating states for training and generating them for measurement pull opposite ways:

exact

TRUE (default) walks n_moves every time, which is what measurement wants: a result is then about that depth and not about a mixture. FALSE draws a length uniformly from 1 to n_moves, the sampling training asks for, spreading accuracy outward from the goal without weighting the loss.

no_undo

TRUE (default) refuses a move that undoes the one before it. generate_state allows those, so its n_moves is an upper bound on the distance — a drawn U U\' quietly costs two moves and travels nowhere. Refusing them makes the label mean more. Longer cycles are left alone: four quarter turns of one face also come home, and refusing every way back would mean searching the group rather than walking it.

pivot

TRUE reports a point partway along each walk instead of its end, with the two moves that meet there. A cut is drawn uniformly from k_min to n_moves - 1 — before the walk, so that every depth is equally represented — and states then holds that point, depth its distance label, and prev_move / next_move name the move back toward the identity and the move the walk went on to make. Those two are the only moves whose value is known at that state — depth - 1 and depth + 1 — which is what a Q-model is trained on. Default FALSE.

no_cancel

TRUE refuses a move that cancels against the tail of the walk through moves it commutes with. On the cube U, D and E commute, so U D U\' walks three moves and travels one, and U has order 4, so U U U is U\'; no_undo lets both through. Commutation and order are read off the permutations, so this works for any group. It includes what no_undo refuses. The length is still an upper bound, only a tighter one. Default FALSE.

Even with no_undo the length stays an upper bound on the true distance to solved: a shorter route may exist that this walk did not take. A solver compared against solution is therefore never credited with a shortcut the reference did not have, which is the safe direction to err in.

Value

A list with

states

integer matrix, n rows, one walk endpoint per row — or the pivot point when pivot = TRUE

depth

integer vector, the length of each walk — or the pivot's distance label when pivot = TRUE

moves

list of n character vectors, the word each walk took

solution

list of n character vectors, each the inverse of the corresponding word — a path from that state to solved. NULL when pivot = TRUE, where the word describes the whole walk and not the reported state.

prev_move, next_move

character vectors, present only when pivot = TRUE: the move back toward the identity and the move away from it

See Also

generate_state when the route is not needed, invert_path, cube_group

Examples

g <- cube_group(3)
w <- generate_walk(g, n = 2, n_moves = 6)
dim(w$states)
w$moves[[1]]

# the reported solution really does solve the state
s <- group_apply(g, w$states[1, ], w$solution[[1]])
identical(s, group_identity(g))

# for training: a spread of depths rather than one
w <- generate_walk(g, n = 5, n_moves = 10, exact = FALSE)
w$depth

# for a Q-model: a midpoint and the two moves whose value is known there
p <- generate_walk(g, n = 3, n_moves = 8, exact = FALSE, pivot = TRUE)
data.frame(depth = p$depth, back = p$prev_move, away = p$next_move)

Random Walks From the Solved State, With the Moves They Took

Description

Walks away from the identity and reports the word it walked, which is what separates this from generate_state and from the ADI scrambler. Knowing the word means knowing a way home — inverting it solves the state — and anything that measures a solver against a reference path needs exactly that.

Usage

generate_walk_cpp(
  group,
  n,
  n_moves,
  exact = TRUE,
  no_undo = TRUE,
  pivot = FALSE,
  k_min = 2L,
  no_cancel = FALSE
)

Arguments

Details

Two switches cover what the callers want, because the two uses pull opposite ways:

exact

TRUE walks n_moves every time. FALSE draws a length uniformly from 1 to n_moves, which is the sampling training asks for: it spreads accuracy outward from the goal without any weighting in the loss. Measurement wants the opposite — a fixed depth, so that a result is about that depth and not about a mixture dominated by states a move or two from solved.

no_undo

TRUE refuses a move that undoes the one before it. Such a pair returns the state to where it was and makes the walk shorter than its label. Longer cycles are left alone: on the cube four quarter turns of one face also come home, and refusing every way back would mean searching the group rather than walking it.

Even with no_undo the length is an upper bound on the distance to solved, never a promise. Callers comparing a solver against the returned word should read it as "no worse than this", which is the safe direction: the solver is never credited with a shortcut the reference did not have.

The walk is uniform over the alphabet, so a group given generators without their inverses is walked with what it has; no_undo then has nothing to refuse at those steps and allows them.

pivot = TRUE changes what is reported without changing how a walk is taken. A cut is drawn uniformly from k_min to n_moves - 1 and the state at that point is returned instead of the endpoint, together with the two moves that meet there: the inverse of the move that arrived (prev_move, a step back toward the identity) and the move the walk went on to make (next_move, a step further away). depth then reports the cut, which is that point's distance label.

The cut is drawn BEFORE the walk, and the walk is then made long enough to contain it. Walking first and cutting inside afterwards is the obvious order, but it leans the labels hard on the shallow end — a cut of 1 can come out of every walk, a deep cut only out of the longest — and the deep end ends up too thin to read while the shallow end, where the task is trivial, dominates the averages. Cutting first gives every depth equal weight, which is what the depth scripts sample and what a by-depth table has to have to be comparable between runs.

This is what a Q-model is trained on. Of the whole alphabet only those two moves have a known label at that state — depth - 1 and depth + 1 — and both come out of the walk itself, with no prefix replayed and no distance guessed. next_move is the move the walk really took, not one drawn afresh, so it is a genuine step of a random walk rather than an arbitrary neighbour. k_min defaults to 2 because a cut of 1 puts the pivot one move from solved, where every method is right and the row says nothing. no_undo keeps next_move from being the inverse of the arriving move, which would otherwise carry both labels at once.

Value

List with states (n x state_len integer matrix, one walk endpoint per row), depth (integer vector, the length of each walk) and moves (n x n_moves integer matrix of 1-based move indices, the word each row walked, padded with NA past that row's depth). With pivot = TRUE it also carries prev_move and next_move (integer vectors of 1-based move indices) and states holds the pivot point rather than the endpoint, with depth its distance label.

Find Cycle in Permutation Group

Description

Explores the Cayley graph starting from an initial state and applying a sequence of operations repeatedly until returning to the start state. Returns detailed information about all visited states, the cycle structure, and celestial LRX coordinates.

Usage

get_reachable_states(start_state, allowed_positions, k, verbose = FALSE)

Arguments

Value

List containing:

Examples

result <- get_reachable_states(1:10, c("1", "3"), k = 4)
writeLines(result$cycle_info)

Find Cycle Length (Lightweight Version)

Description

Fast version of cycle detection that only returns cycle length and unique state count without storing all intermediate states. Useful for testing many operation sequences efficiently. Implemented in C++ for performance.

Usage

get_reachable_states_light(
  start_state,
  allowed_positions,
  k = NULL,
  group = NULL,
  max_moves = 10000000L
)

Arguments

Value

List containing:

Examples

result <- get_reachable_states_light(1:10, c("1", "3"), k = 4)
cat("Cycle length:", result$total_moves, "\n")
cat("Unique states:", result$unique_states_count, "\n")

# the order of the sexy move, the long way round
g <- cube_group(3)
get_reachable_states_light(group_identity(g), "R U R' U'", group = g)

Apply a Move Sequence Through a Group

Description

Applies moves left to right. Moves may be named or given as indices into the group's alphabet.

Usage

group_apply(group, state, moves)

Arguments

Value

Integer vector, the state after the moves

See Also

group_compose, group_inverse_seq

Examples

g <- cube_group(3)
s <- group_apply(g, group_identity(g), "R U R' U'")
sum(s != group_identity(g))

tg <- topspin_group(6, k = 3)
group_apply(tg, 1:6, c("1", "1", "3"))

Compose a Move Sequence into One Permutation

Description

Multiplies a word out into a single permutation of 1:n. Applying that permutation once does what the whole word does, which is what makes repeating a word cheap.

Usage

group_compose(group, moves)

Arguments

Value

Integer vector of length n, the composed permutation

See Also

group_apply, group_order

Examples

g <- cube_group(3)
p <- group_compose(g, "R U R' U'")
identical(group_identity(g)[p], group_apply(g, group_identity(g), "R U R' U'"))

Solved State of a Group

Description

The identity, 1:n, for whatever n the group works on.

Usage

group_identity(group)

Arguments

Value

Integer vector of length n

Examples

group_identity(topspin_group(6, 3))
length(group_identity(cube_group(3)))

Invert a Move Sequence

Description

The word that undoes the given one: reversed, each move replaced by its inverse. Errors if some move's inverse is not in the group's alphabet.

Usage

group_inverse_seq(group, moves, as_names = TRUE)

Arguments

Value

The inverse sequence, as names or indices

See Also

group_apply

Examples

g <- cube_group(3)
group_inverse_seq(g, "R U R' U'")

# a word and its inverse cancel
s <- group_apply(g, group_identity(g), "R U U F'")
identical(group_apply(g, s, group_inverse_seq(g, "R U U F'")), group_identity(g))

Resolve Move Names to Indices Within a Group

Description

Accepts moves however they are spelled — names, indices, or one space-separated string — and returns indices into the group's alphabet. Every function taking a moves argument runs it through here, which is why names and indices are interchangeable everywhere.

Usage

group_move_index(group, moves = NULL)

Arguments

Details

Names are matched against the alphabet the group was built with, so a TopSpin group made with the default c("1","2","3") spelling does not answer to "L": build it with moves = c("L","R","X") if that is the spelling you want to use.

Value

Integer vector of 1-based move indices

See Also

group_moves

Examples

g <- cube_group(3)
group_move_index(g, "R U R' U'")
group_move_index(g, c(4, 1, 5, 2))

# names resolve against the alphabet the group was built with
tg <- topspin_group(10, 4, moves = c("L", "R", "X"))
group_move_index(tg, c("L", "X"))

# the default spelling is "1","2","3", so those are its names
group_move_index(topspin_group(10, 4), c("1", "3"))

Move Alphabet of a Group

Description

Move Alphabet of a Group

Usage

group_moves(group)

Arguments

Value

Character vector of move names

Examples

group_moves(topspin_group(10, 4))
group_moves(cube_group(3))

Order of a Move Sequence in a Group

Description

How many times a word must be repeated before the state returns to where it started. This is the order of the word as a group element, and does not depend on the starting state.

Usage

group_order(group, moves, max_reps = 100000L)

Arguments

Value

Integer, the order, or NA if max_reps was reached

See Also

group_compose

Examples

g <- cube_group(3)
group_order(g, "R")
group_order(g, "R U")
group_order(g, "R U R' U'")

Parse a Word Written as One String

Description

Combination words have always been written unseparated — "1231" is four TopSpin operations — which reads only because each move is one character. A cube's moves are not: "R'M'" has to be split on its move names, not its characters. This does both, longest name first, so a group's own spelling always wins over a shorter prefix of it.

Usage

group_parse_word(group, word)

Arguments

Value

For one string, an integer vector of move indices; for a vector, a list of them

See Also

group_move_index

Examples

group_parse_word(topspin_group(10, 4), "1231")
group_parse_word(cube_group(3), "RM'R'")
group_parse_word(cube_group(3), "R M' R'")

Solve a State with the Human TopSpin Algorithm

Description

Reproduces the way a person solves TopSpin by hand. A sorted run is grown one value at a time: for each new value m the ring is manoeuvred until m sits exactly k positions after m-1, so that a single reverse-prefix drops m directly behind m-1. Auxiliary flips are restricted to windows lying wholly inside the unsorted arc, so the run is never disturbed.

Usage

human_algorithm(start_state, final_state = NULL, k = 4L, simplify = TRUE)

Arguments

Details

Once the tail is down to eight tiles the insertion move no longer fits, and the tail is finished with two local 3-cycles built from the same operations (XLXLXRX and LXRXLXLX, each with a compensating rotation). Their conjugates generate the full alternating group on the tail, so any even arrangement is reachable by table lookup rather than search.

Because 3-cycles are even permutations, odd tail arrangements are out of their reach. In that case a single flip is fired across the block boundary and the run is rebuilt: moving one tile between block and tail changes the parity of the split, after which the table applies.

Value

List with components:

Examples

set.seed(1)
s <- generate_state(20, k = 4, n_moves = 50)
res <- human_algorithm(s, k = 4)
res$found

Human Algorithm Path Between Two Arbitrary States

Description

Finds a path from start_state to target_state with the same human TopSpin method as human_algorithm, but without routing through the identity state.

Usage

human_algorithm_to(start_state, target_state = NULL, k = 4L, simplify = TRUE)

Arguments

Details

human_algorithm reaches an arbitrary target by solving both endpoints to 1:n and concatenating the first path with the inverse of the second, so the word is roughly twice as long as it needs to be. Here the problem is instead relabelled: because the three operations permute positions and treat the values as inert labels, renaming every value v to its position in target_state turns "reach target_state" into "reach 1:n". The solver then runs once on the relabelled state and the resulting word applies unchanged to the original one.

Formally, with inv the inverse permutation of the target (inv[target_state] == seq_len(n)), the relabelled state is inv[start_state]. Any word P sorting it satisfies P(inv[start_state]) == 1:n, and since P acts on positions it commutes with the elementwise relabelling, giving P(start_state) == target_state.

Value

List with components:

See Also

human_algorithm

Examples

set.seed(1)
s <- generate_state(20, k = 4, n_moves = 50)
t <- generate_state(20, k = 4, n_moves = 50)
res <- human_algorithm_to(s, t, k = 4)
res$found

Follow the Phase 1 Navigator to the Tail

Description

Repeatedly applies the move human_phase1_rank prefers, growing the sorted run until phase 1 runs out of applicable moves – that is, until only the tail is left. The tail itself is not touched; finishing it needs either the 3-cycles of human_algorithm or a search such as find_path_iterative.

Usage

human_phase1_navigate(state, k = 4L, max_steps = 2000L, trace = FALSE)

Arguments

Details

The walk is greedy: at each step the single best-ranked candidate is taken.

Value

List with components:

See Also

human_phase1_rank, human_algorithm

Examples

set.seed(42)
s <- generate_state(20, k = 4, n_moves = 200)
nav <- human_phase1_navigate(s, k = 4)
nav$run

Rank Candidate Moves by the Phase 1 Criterion

Description

Exposes phase 1 of human_algorithm as a navigator: instead of committing to a move, it reports the moves phase 1 would consider from the given state, each scored. A search can use this to choose its own direction while still being guided by the human method.

Usage

human_phase1_rank(state, k = 4L, sorted = TRUE)

Arguments

Details

The candidates are composite moves – "rotate the ring so the flipper covers a chosen window, then flip" – which is the unit phase 1 actually works in. Ranking the three raw operations instead would give no signal: a single rotation changes neither the run nor the gap. One candidate is produced per window offset, plus the placing move itself when the gap already equals k. Windows that would overlap the finished run are dropped, exactly as in phase 1.

With sorted = TRUE the rows come back in phase 1's own order of preference: run descending, then gap_cost ascending, then the shorter word.

An empty data frame is returned once the run has grown far enough that only the tail is left: the insertion move no longer fits there, and the tail needs the 3-cycles of phase 2 instead.

Value

A data.frame with one row per candidate move:

See Also

run_length, human_algorithm

Examples

set.seed(1)
s <- generate_state(20, k = 4, n_moves = 50)
human_phase1_rank(s, k = 4)

Invert a Path of Operations

Description

Reverses a sequence of operations and replaces each by its inverse, giving the path that undoes the original. For TopSpin that means "1" (shift left) becomes "2" (shift right) and vice versa, while "3" (reverse) is its own inverse; for any other perm_group the group says which move undoes which.

Usage

invert_path(path, group = NULL)

Arguments

Value

Character vector of inverted operations in reverse order

See Also

group_inverse_seq

Examples

invert_path(c("1", "3", "2"))
invert_path(c("1", "1", "3"))

invert_path(c("R", "U", "U", "F'"), group = cube_group(3))

Test Whether an Object is a Permutation Group

Description

Test Whether an Object is a Permutation Group

Usage

is_perm_group(x)

Arguments

Value

Logical

Examples

is_perm_group(topspin_group(10, 4))
is_perm_group(1:10)

The 4x4x4 reduction phases, one call at a time

Description

The reduction that turns a 4x4x4 into a 3x3x3 runs in three phases, and these expose them individually. cube_kociemba4_reduce runs all three and reports only the result; these let a caller stop after any one of them, inspect what it produced, and decide what to do next – which is what cube_solve4_cascade does, and what every diagnostic in inst/examples was written against.

Usage

cube_kociemba4_phase12_cpp(state, upto_phase = 2L, max_depth1 = 10L,
  max_depth2 = 12L, node_budget = 5e7)

cube_kociemba4_phase3_cpp(state, max_depth3 = 14L, node_budget = 5e7,
  prune_depth_bonus = 0L, use_exact_centres = FALSE, progress_every = 0)

cube_at_phase_goal_cpp(state, phase)

cube_phase3_coord_cpp(state)

cube_to_pieces4_cpp(state)

cube_wing_geometry_cpp()

cube_kociemba4_tables_cpp()

cube_kociemba4_fill_phase3_cpp(depth, table_size = 0, breadth_first = TRUE,
  max_frontier = 4e+07)

Arguments

Value

cube_kociemba4_phase12_cpp returns the moves as a character vector.

cube_kociemba4_phase3_cpp returns a list: found, path, generators (the phase's own move words, which expand to path), states_perm and states_ori (the states the search passed through, one row per generator), outcome, best_bound, nodes and the prune counters. On failure the path and states describe the branch the table rated closest, which is where the effort went rather than progress towards a solution.

cube_at_phase_goal_cpp returns a single logical.

cube_phase3_coord_cpp returns phase 3's coordinate broken into parts, including prune_bound – which is only meaningful once the table has been built, so a fresh process reports it as 0 or 1 for everything.

cube_to_pieces4_cpp returns perm and ori: the 56-piece vector, with corners at 1:8, wings at 9:32 and centres at 33:56. Values carry the same offsets, so a wing's number runs 8..31 rather than 0..23.

cube_wing_geometry_cpp returns the wing geometry: partner, dedge, primary, primary_in_dedge and speffz_to_slot, all measured from the cube rather than tabulated.

cube_kociemba4_tables_cpp returns one entry per phase describing its prune table: size, filled, built_depth, n_collisions, waste_ratio and the per-depth counts.

See Also

cube_kociemba4_reduce for all three phases at once, cube_solve4_cascade for the bounded version that falls back.

Generate Landmark States for a Permutation of Size n

Description

Builds 25 structurally distinct permutations of 1:n, each defined by a rule rather than by a random draw, so the same construction can be compared across different n. They serve as landmarks (fixed probe points) in the Cayley graph: the distance from the identity to each landmark, measured for several small n where the diameter is known, gives a ratio d / diameter that can be extrapolated to larger graphs.

Usage

landmark_states(n)

Arguments

Details

The constructions, in the order returned:

1. full_reverse — \sigma(j) = n + 1 - j, the maximum number of inversions.

2. block_swap — the first half and the last half exchange places. For odd n the middle element stays put.

3. riffle — perfect interleaving of the two halves: 1, h+1, 2, h+2, \ldots with h = \lceil n/2 \rceil.

4. envelope — taken alternately from the two ends towards the centre: n, 1, n-1, 2, \ldots.

5. adjacent_swaps — the full pairing of neighbours: swap(1,2), swap(3,4), ... A trailing odd element is left alone.

6. broken_cycle — the n-cycle 2,3,\ldots,n,1 with the last two entries exchanged.

7. zigzag — all odd values ascending, then all even values descending.

8. block_rotate3 — the sequence cut into three blocks ABC of deliberately unequal length and reassembled as CAB. Equal blocks would make this a plain rotation, i.e. one L move from the identity.

9. two_cycles — two independent cyclic shifts, one inside each half.

10. shift_reverse — a left shift by 2 followed by reversing the first 4 elements.

11. pair_shift — odd positions take the value two ahead, wrapping round the odd positions only.

12. reverse_first — the first half reversed, the second fixed.

13. reverse_second — the first half fixed, the second reversed.

14. spiral — 1, n, 2, n-1, \ldots, alternating from the two ends but starting at the bottom.

15. local_block — a single block of four rotated in place, every other tile untouched.

16. single_swap — one transposition in the middle; the permutation closest to the identity in this set.

17. faro_in — the mirror of riffle: the upper half leads the interleaving.

18. block_reverse_pairs — the pairs (1,2)(3,4)... kept intact but listed in reverse block order.

19. doubling — \sigma(j) = 2j \bmod (n+1). That is a bijection only for even n; for odd n the map runs on 1..n-1 modulo n and the last tile stays put.

20. shift_third — a shift by n/3 with the displaced block reversed.

21. double_riffle — the halves interleaved two elements at a time rather than one.

22. cycles3 — 3-cycles (1 2 3)(4 5 6)... with any tail fixed.

23. alt_pairs — every other pair reversed: swap(1,2), leave (3,4), swap(5,6), ...

24. cascade — swapped pairs offset by one as they march along, like falling dominoes.

25. derangement — the halves exchanged and then every fixed point displaced, so no tile keeps its own place. Reversing one half instead would only reproduce reverse_first rotated by n/2.

At n = 6 cycles3 degenerates into two_cycles; for every n from 7 upwards all 25 states are distinct.

Value

A data.frame with one row per landmark and columns id, name, description, state_str (underscore-joined) and state (a list column holding the integer vector).

Examples

landmark_states(10)$state_str

Manhattan Distance Between Two States

Description

Computes the sum of absolute differences between corresponding elements of two permutation states.

Usage

manhattan_distance(start_state, target_state)

Arguments

Value

Numeric, the Manhattan distance

Examples

manhattan_distance(1:5, 5:1)
manhattan_distance(1:5, 1:5)

Compute Pairwise Manhattan Distance Matrix on GPU

Description

Computes all pairwise Manhattan distances between two sets of states. Returns an N1 x N2 matrix where entry (i,j) is the Manhattan distance between row i of states1 and row j of states2.

Usage

manhattan_distance_matrix_gpu(states1, states2, batch_size = 256L)

Arguments

Details

For large matrices, computation is batched over columns of the result to avoid GPU memory overflow.

Value

Numeric matrix (N1 x N2) of Manhattan distances

Examples

if (cayley_gpu_available()) {
  s1 <- matrix(c(1,2,3,4,5, 5,4,3,2,1), nrow = 2, byrow = TRUE)
  s2 <- matrix(c(3,3,3,3,3, 1,1,1,1,1), nrow = 2, byrow = TRUE)
  manhattan_distance_matrix_gpu(s1, s2)
}

Number of OpenMP Threads Available

Description

Reports how many threads OpenMP would use by default, which is the core count unless OMP_NUM_THREADS says otherwise. Returns 1 when the package was built without OpenMP.

Usage

openmp_threads()

Details

Useful for sizing the n_threads argument of cycle_shortcut, whose own default is two below this number.

Value

Integer, the thread count

Examples

openmp_threads()

Create a Permutation Group from a Table of Moves

Description

Declares a group by listing its moves as explicit permutations. This is the general constructor: any puzzle whose moves permute a fixed set of positions can be expressed here, with no C++ involved.

Usage

perm_group(perms, n = NULL, name = "perm_group")

Arguments

Value

An object of class perm_group

See Also

topspin_group, cube_group, perm_group_intro

Examples

# the 3x3x3 cube, from the table the package already ships
g <- perm_group(cube_moves(3), n = 54, name = "cube3")
g

# a group of your own: two generators on five points
g2 <- perm_group(list(
  a = c(2L, 3L, 4L, 5L, 1L),
  b = c(2L, 1L, 3L, 4L, 5L)
))
group_moves(g2)

Permutation Groups

Description

A perm_group is what the rest of the package means by "the puzzle being solved": a state length, an alphabet of named moves, and a way to apply one. Search functions take a group and work through it, so the same BFS, the same store and the same iterative solver run over TopSpin, over the 3x3x3 cube, or over any group you declare yourself.

Details

Two constructors cover the built-in puzzles — topspin_group and cube_group — and perm_group itself takes an arbitrary table of permutations, which is how a new puzzle enters without a line of C++.

What a group must supply

Moves are given as permutations of 1:n, each read as new[i] <- state[perm[i]]: entry i says where position i draws its new value from. This is the same convention cube_moves is written in, so that table can be handed over unchanged.

Inverses are worked out by composition, not by naming, so you need not say which move undoes which. A move whose inverse is absent from the alphabet is recorded as having none, and functions that need to walk a path backwards will say so rather than guess.

Moves versus alphabet

The group fixes the alphabet; a search may use any subset of it. Every search function still takes moves, now naming a subset of the group's moves rather than defining them. Leaving it out means the whole alphabet.

See Also

perm_group, topspin_group, cube_group

Print a Permutation Group

Description

Shows the group's name, the length of the states it works on, and its move alphabet.

Usage

## S3 method for class 'perm_group'
print(x, ...)

Arguments

Value

x, invisibly

See Also

perm_group, group_moves

Examples

print(topspin_group(12, k = 4))
cube_group(3)

Process Final-type Intersection

Description

Handles an intersection where the meeting state equals the original final state. Reconstructs path through the start (forward) search tree.

Usage

process_final_intersection(
  intersection_state,
  reachable_states_start,
  bridge_states_start,
  start_index,
  v_cols
)

Arguments

Value

List with path and info, or NULL

Process Intermediate Intersection

Description

Handles a general intersection found in both forward and backward search trees. Combines paths from both directions.

Usage

process_intermediate_intersection(
  intersection_state,
  reachable_states_start,
  reachable_states_final,
  bridge_states_start,
  bridge_states_final,
  start_index,
  final_index,
  v_cols
)

Arguments

Value

List with path and info, or NULL

Process Start-type Intersection

Description

Handles an intersection where the meeting state equals the original start state. Reconstructs path through the final (backward) search tree.

Usage

process_start_intersection(
  intersection_state,
  reachable_states_final,
  bridge_states_final,
  final_index,
  v_cols
)

Arguments

Value

List with path and info, or NULL

Reconstruct path from sparse BFS result

Description

Traces back from target_key to the root (start state) using the parent_key/child_key edges in the BFS result.

Usage

reconstruct_bfs_path(bfs_result, target_key)

Arguments

Value

Character vector of operations from start to target

Reconstruct Full Path Through Cycle Chain

Description

Traces back through a chain of cycles to build the full operation path from the initial state to a target state.

Usage

reconstruct_full_path(
  reachable_states,
  start_state,
  target_state,
  target_cycle,
  target_combo,
  v_cols
)

Arguments

Value

Character vector of operations, or NULL on error

Reverse First k Elements (with Coordinates)

Description

Reverses the first k elements of the state vector (turnstile operation). Tracks celestial coordinates (LRX momentum).

Usage

reverse_prefix(state, k, coords = NULL)

Arguments

Value

List with components:

Examples

result <- reverse_prefix(1:10, k = 4)
result$state

Reverse First k Elements (Simple)

Description

Simple prefix reversal without coordinate tracking.

Usage

reverse_prefix_simple(state, k)

Arguments

Value

Integer vector with first k elements reversed

Examples

reverse_prefix_simple(1:10, k = 4)

Length of the Sorted Run on the Ring

Description

Returns the length of the run 1, 2, ..., r currently sitting consecutively on the ring, starting wherever value 1 happens to be. This is the quantity phase 1 of human_algorithm maximises: each insertion move appends one value to the run.

Usage

run_length(state)

Arguments

Details

Because the ring is cyclic, the position of value 1 is irrelevant – only the consecutive run following it is counted. A fully sorted state gives n; a state where 2 does not follow 1 gives 1.

Value

Integer, length of the sorted run (0 if value 1 is absent)

See Also

human_phase1_rank, human_algorithm

Examples

run_length(1:20)                  # 20, fully sorted
run_length(c(1:5, 20:16, 6:15))   # 5

Save Bridge States to CSV

Description

Writes a list of bridge states (each with state and cycle fields) to a CSV file.

Usage

save_bridge_states(bridge_states, filename)

Arguments

Value

Invisible NULL. Side effect: writes a CSV file.

Examples

bs <- list(
  list(state = 1:5, cycle = 0),
  list(state = c(2, 1, 3, 4, 5), cycle = 1)
)
# save_bridge_states(bs, tempfile(fileext = ".csv"))

Select New Bridge State

Description

Selects a new state from candidate states that is close to an opposite state (by Manhattan distance). Randomly picks from the top 10 closest.

Usage

select_new_state(target_all, opposite_state, method = "manhattan")

Arguments

Value

Integer vector of the selected state

Select Unique States by V-columns

Description

Removes duplicate rows based on state columns (V1, V2, ..., Vn).

Usage

select_unique(df)

Arguments

Value

Data frame with unique states

Examples

df <- data.frame(V1 = c(1, 1, 2), V2 = c(2, 2, 1), op = c("a", "b", "c"))
select_unique(df)

Shift State Left (with Coordinates)

Description

Performs a cyclic left shift on the state vector, moving the first element to the end. Tracks celestial coordinates (LRX momentum).

Usage

shift_left(state, coords = NULL)

Arguments

Value

List with components:

Examples

result <- shift_left(1:5)
result$state
result$coords

# Chain operations using coords
r1 <- shift_left(1:5)
r2 <- shift_left(r1$state, r1$coords)
r2$coords$nL

Shift State Left (Simple)

Description

Simple cyclic left shift without coordinate tracking.

Usage

shift_left_simple(state)

Arguments

Value

Integer vector with elements shifted left by one position

Examples

shift_left_simple(1:5)

Shift State Right (with Coordinates)

Description

Performs a cyclic right shift on the state vector, moving the last element to the front. Tracks celestial coordinates (LRX momentum).

Usage

shift_right(state, coords = NULL)

Arguments

Value

List with components:

Examples

result <- shift_right(1:5)
result$state

Shift State Right (Simple)

Description

Simple cyclic right shift without coordinate tracking.

Usage

shift_right_simple(state)

Arguments

Value

Integer vector with elements shifted right by one position

Examples

shift_right_simple(1:5)