cayleyR

cayleyR is an R package for analyzing Cayley graphs of permutation puzzles. The package implements algorithms for cycle detection, state space exploration, bidirectional BFS pathfinding, and finding optimal operation sequences. Two families of puzzle are built in: TopSpin, whose group is generated by shift and reverse operations, and Rubik's cubes of any size, whose moves are generated from the geometry — a turn of one layer about one axis. Both are handled in the same terms — a state is an integer vector, a move permutes it.

The core method — Iterative Cycle Intersection (ICI), implemented in find_path_iterative() — grows cycles from both endpoints and looks for states where the two sides meet, using the meeting points as bridges to narrow the search. It is described in the accompanying paper: CayleyR: Solving the TopSpin puzzle via cycle intersection.

Features

• Basic permutation operations (C++): cyclic left/right shifts, prefix reversal
• Rubik's cubes of any size (C++): moves generated from the geometry, so the 3x3x3 slice turns and the inner layers of a 4x4x4 follow from the same rule as the faces; scrambling, inversion, cycle unrolling and a console net for the 3x3x3
• Five solving methods for the 3x3x3 (C++): four human ones -- CFOP and layer by layer, which solve by looking, and the blindfolded Old Pochmann and M2, which place one piece at a time by conjugation and never look at the cube after the start -- plus a two-phase search after Kociemba, which is not a human method at all and reaches the same cube in a quarter of the moves
• Cycle analysis: find cycles in Cayley graphs with detailed state information
• Sequence optimization: search for operation sequences with flexible sorting criteria
• C++ StateStore: compact hash-indexed state storage with O(1) incremental insert and O(min(N,M)) intersection
• Bidirectional BFS: find shortest paths between permutation states
• Iterative solver (ICI): find paths between arbitrary states via Iterative Cycle Intersection — expand cycles from both ends and bridge them at shared states
• BFS highway solver: combine sparse BFS trees with iterative solver, auto-selects direct vs hub path
• Human-style solver: solve the way a person does — grow a sorted run, then finish the tail with derived cycle primitives
• Relabelling solver: reach an arbitrary target in one pass instead of routing through the sorted state, roughly halving the word
• Cycle shortcut: shorten a path by cutting across cycles that leave it and rejoin it further along (OpenMP)
• Graph metrics: full BFS over the reachable component, and graph diameter by all-pairs or sampling
• Landmark states: 25 permutations defined by rules rather than by chance, as fixed probe points in graphs too large to enumerate
• Hull geometry: convex hull of a point cloud, or a non-convex one passing through every point, with surface area and volume
• 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

Installation

# From GitHub:
devtools::install_github("Zabis13/cayleyR")

Quick start

library(cayleyR)

# Basic operations
state <- 1:10
shift_left(state)              # cyclic left shift
shift_right(state)             # cyclic right shift
reverse_prefix(state, k = 4)  # reverse first 4 elements

# Apply a sequence of operations
apply_operations(state, c("L", "R", "X"), k = 4)

# Find cycle length for an operation sequence
get_reachable_states_light(state, c("1", "3"), k = 4)

# Find best random operation sequences (flexible sorting)
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")  # or "longest", "most_repeated", etc.
)

# Bidirectional BFS shortest path
bidirectional_bfs(start = 1:10, target = c(2:10, 1), k = 4)

# Iterative path finder
find_path_iterative(
  start_state = 1:10,
  final_state = c(3, 1, 2, 4, 5, 6, 7, 8, 9, 10),
  k = 4,
  sort_by = c("longest", "most_unique")
)

# BFS highway path finder (auto-selects direct vs hub route)
find_path_bfs(
  start_state = 1:10,
  final_state = c(3, 1, 2, 4, 5, 6, 7, 8, 9, 10),
  k = 4,
  bfs_levels = 200,
  sort_by = c("longest", "most_unique")
)

# Human-style solver: sort a scrambled ring the way a person would
state <- generate_state(20, k = 4, n_moves = 60)
res <- human_algorithm(state, k = 4)
res$found
res$path

# Or aim at an arbitrary target instead of 1:n
human_algorithm(state, final_state = c(2:20, 1), k = 4)

The 3x3x3 cube

A cube state is an integer vector of length 54, one entry per sticker, and a move permutes it — the same shape of object the TopSpin side works with. Stickers are numbered face by face (U 1–9, R 10–18, F 19–27, D 28–36, L 37–45, B 46–54), so the solved cube is 1:54. The six centres never move.

# the eighteen moves: twelve face turns and three slices
names(cube_moves(3))
#>  [1] "U"  "U'" "R"  "R'" "F"  "F'" "D"  "D'" "L"  "L'" "B"  "B'"
#> [13] "M"  "M'" "E"  "E'" "S"  "S'"

# apply a sequence, then undo it
g <- cube_group(3)
s <- group_apply(g, cube_identity(3), "R U R' U'")
identical(group_apply(g, s, group_inverse_seq(g, "R U R' U'")),
          cube_identity(3))
#> TRUE

# how long a word takes to come back round
group_order(g, "R U")           # 105
group_order(g, "R U R' U'")     # 6

Sequences go through the group API — group_apply(), group_compose(), group_order(), group_inverse_seq() — which is the same set of functions TopSpin uses, and works on any cube size.

The alphabet is the quarter-turn metric: half turns are not moves of their own, so R2 is the word c("R", "R"). The choice matters because it is what a shortest path is counted in — the face group has diameter 20 counting half turns as one move, and 26 counting them as two.

# any cube size, from the same generator
names(cube_moves(2))    # 12: face turns only, no slices
names(cube_moves(4))    # 24: face turns plus numbered inner layers
names(cube_moves(5))    # 30

# a single layer about an axis, by number
identical(cube_layer_move(3, axis = 1, layer = 2, turns = 1),
          cube_moves(3)[["M"]])
#> TRUE

Codes group by face in threes — clockwise, anticlockwise, half turn — so (code - 1) %/% 3 is the face and (code - 1) %% 3 the kind of turn, which makes inverting a move arithmetic rather than string work.

cube3_cycle() is the cube counterpart of the cycle expansion the ICI solver is built on: it spins a word round and round from a starting state, collecting every state it passes through, until the state returns to where it began. A short word reaches states far from its start without a BFS frontier having to hold them.

cyc <- cube3_cycle(cube3_identity(), "R U")
cyc$order          # 105 repetitions to close
dim(cyc$states)    # 105 x 54, every state on the loop

Cubes of any size

A move is an axis, a layer along it, and a quarter turn. That vocabulary covers every cube, so the permutations are generated from the geometry rather than tabulated: a cube of side n has 6n^2 stickers and 6n moves.

cube_group(2)                 # 24 stickers, 12 moves
cube_group(3)                 # 54 stickers, 18 moves
cube_group(4)                 # 96 stickers, 24 moves

cube_move_names(3)
#>  [1] "U"  "U'" "R"  "R'" "F"  "F'" "D"  "D'" "L"  "L'" "B"  "B'"
#> [13] "M"  "M'" "E"  "E'" "S"  "S'"

The 3x3x3 slice turns are not a special case: the three layers of an axis are two faces and the slice between them, so M, E and S come out of the same rule as R and L. Inner layers of larger cubes have no standard letter and are written axis-and-index, "1x" being layer 1 along x.

Half turns are words rather than letters here — U2 is "U U". This is the quarter-turn metric, and it is what a shortest path gets counted in; the cube3_* functions above keep half turns as single moves instead.

Once slices are in play the centres move, and a cube turned bodily in space is solved without its stickers being back where they started:

g <- cube_group(3)
s <- group_apply(g, cube_identity(3), c("R", "M'", "L'"))   # the whole cube turns
cube_is_colour_solved(s)          # TRUE  — every face one colour
identical(s, cube_identity(3))    # FALSE — but the stickers moved

The generated table is checked against the hand-written 3x3x3 one, which it reproduces entry for entry, and the 2x2x2 against its published state counts per depth.

Solving the 3x3x3 the way people do

Four methods, all taking a reachable 54-sticker state and returning the same four things — path, found, stages, states — so they can be swapped for one another and compared.

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

cube_solve_cfop(s)$path           # cross, F2L, OLL, PLL
cube_solve_lbl(s)$path            # layer by layer
cube_solve_old_pochmann(s)$path   # blindfolded, one piece at a time
cube_solve_m2(s)$path             # blindfolded, cheaper edges
cube_kociemba(s)                  # two-phase search, the fewest moves

They split in two on one question: does the method look at the cube while it runs? CFOP and layer by layer do — a stage ends when the cuber can see that it has, and a move is chosen for the position in front of them, so one move can serve several pieces at once. The two blindfolded methods never look after the start. That forces a single repeated step whose shape is always the same: swap whatever is in the buffer with one chosen piece, disturb nothing else. Nothing is searched. Each piece is placed by a conjugate — setup moves that bring the target where the algorithm can reach it, one memorised algorithm, the setups undone.

The algorithms used are ordinary PLLs, because "swap two edges and two corners" is exactly what a T-perm does. The second swap is not incidental: a single swap is an odd permutation and the cube group has none, so the spare swaps cancel in pairs and the leftover when their count is odd is the parity step, between the edges and the corners.

cube_solve_m2() is the usual next thing a blindfold solver learns. The corners are Old Pochmann's; the edges are not. Where an edge cost a whole PLL wrapped in setups, the buffer is DF and the swap is M2 — two moves. 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 also moves the centres and exchanges UF/DB. Those two edges 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 parity needs fixing is decided by reading the edge permutation rather than by counting swaps — a chain that breaks into a new cycle spends turns the tally does not see. The cube comes back solved relative to the centres, which is what the method means by solved and what a real cube looks like.

What it costs to not look

Ten scrambled states, 985 moves from solved, every method solving all ten (inst/examples/demo_cube3_solve.R):

method	solved	mean moves	after shortening	mean sec	vs KociembaMod
KociembaMod	10/10	40.4	40.0	1.03	1.00x
CFOP	10/10	103.0	94.0	0.04	2.55x
LBL	10/10	169.2	154.6	0.06	4.19x
M2	10/10	277.6	254.2	0.09	6.87x
Old Pochmann	10/10	432.6	399.0	0.14	10.71x

The baseline is the shortest of them, so the last column reads as "how many times longer". The ordering is the methods' own, and each step down it gives up something the one above relied on.

KociembaMod is apart from the other four: it is the only one that searches the cube rather than following a method, and the only one whose word cannot be explained move by move. It is also the only one the shortener barely improves — 40.4 to 40.0 — because a searched phase has no seams to cut, while a method that finishes each stage before looking at the next leaves a turn and its inverse at every join.

Among the four human methods, CFOP is cheapest in moves because it pairs a corner with its edge and inserts both at once. Blindfolded costs about three to five times CFOP, and the reason is structural rather than a matter of tuning — no move does two things at once when the method may not look at what it is doing. M2 buys back a third of that, all of it on the edges.

tests/testthat/test-cube-kociemba.R checks the search at four scramble lengths, slice moves included.

Landmark states and the solid they span

A Cayley graph at n = 20 has 20! vertices, so nothing about it can be measured by enumeration. landmark_states() gives a set of fixed probe points instead: 25 permutations defined by rules that generalise across n — a full reversal, a riffle shuffle, the doubling map 2j mod (n+1), and so on — so the same construction can be compared between graph sizes.

lm <- landmark_states(20)
lm[, c("name", "state_str")]

Rotations are free

Two constructions can be different permutations and still be the same point of the graph. An early version of derangement looked like this next to reverse_first:

reverse_first:  10 9 8 7 6 5 4 3 2 1 | 11 12 ... 20
derangement:    11 12 ... 20 | 10 9 8 7 6 5 4 3 2 1

One has eight fixed points, the other none — but they are the same sequence cut at a different place, and cutting the ring elsewhere is exactly what L does. The two sat 7 moves apart at n = 14, against a mean of 133. block_swap, block_rotate3 and shift_third collided for the same reason.

Fixing the formulas by hand did not work: each correction collided with something else. landmark_states() now detects collisions instead — it reduces every state to its lexicographic minimum over all n rotations and breaks a tie by transposing one adjacent pair in the later construction. Verified distinct for every n from 6 to 20. The cost is that a state may differ by one transposition from its stated formula.

Distances between landmarks

Use human_algorithm_to(), not human_algorithm(). The latter reaches an arbitrary target by solving both endpoints down to 1:n and splicing the first word with the inverse of the second, so every route detours through the identity — measurably so: the path from envelope to riffle at n = 20 passes a state with 11 of 20 tiles already home.

a <- lm$state[[match("full_reverse", lm$name)]]
b <- lm$state[[match("riffle", lm$name)]]

human_algorithm_to(a, b, k = 4)$length          # direct
human_algorithm(a, final_state = b, k = 4)$length  # via the identity

pair (n = 20)	via identity	direct
two_cycles — full_reverse	441	141
envelope — riffle	329	146

Switching solvers moved the median of all 300 pairwise distances from 238.5 to 158, which in turn changed which pairs count as far apart.

The solid

Twelve points in space bound a figure. convex_hull_3d() gives the smallest convex body containing them, but convexity means some points end up strictly inside and are not corners. enclosing_hull_3d() dents that hull inwards until every point is a vertex.

cube <- as.matrix(expand.grid(c(0, 1), c(0, 1), c(0, 1)))
convex_hull_3d(cube)[c("area", "volume")]      # 6 and 1

withcentre <- rbind(cube, c(0.5, 0.5, 0.5))
h <- enclosing_hull_3d(withcentre)
length(h$vertices)                             # 9 -- the centre is a corner too
c(h$area, h$volume)                            # 6.5607 and 0.9167

The dent costs volume and adds area, as it should. Both functions are implemented in the package rather than taken from geometry, keeping the dependency list at Rcpp alone; they are checked against a cube, a box, a tetrahedron and a regular icosahedron and agree to six decimal places.

Measured on twelve landmarks chosen to be far apart:

	n = 20 convex	n = 20 enclosing	n = 50 convex	n = 50 enclosing
vertices	11 of 12	12 of 12	11 of 12	12 of 12
faces	18	20	18	20
surface area	5 950.57	5 956.42	530 374.12	531 911.41
volume	14 173.83	14 165.50	6 141 465.83	5 928 340.50

A caveat worth stating plainly: a landmark's position comes from the celestial coordinates of the route that reached it, and that route is not guaranteed shortest. These numbers describe a particular set of walks under a particular solver — comparable across n or across solver changes, but not an invariant of the graph.

Running it

source(system.file("examples", "demo_landmark_network.R", package = "cayleyR"))
source(system.file("examples", "demo_landmark_paths.R", package = "cayleyR"))

The first measures the distances, picks disjoint pairs that are far apart, and draws either the paths or the solid; the second draws the star of paths from the identity out to each landmark. Parameters sit in a block at the top of each: N, the layout (celestial, spectral, diffusion), and how landmarks are selected. See vignette("landmark-geometry") for the full pipeline.

C++ StateStore

The core state storage uses a compact C++ backend for high-performance state accumulation during iterative search:

# Create store for permutations of length 10
store <- create_state_store(10L)

# Analyze combos directly into store (no intermediate data.frames)
store_analyze_combos(store, top_combos, start_state, k = 4, cycle_val = 1L)

# Hash-based intersection between two stores: O(min(N,M))
common_keys <- store_find_intersections(store_start, store_final)

# Manhattan distance best match on flat integer array
best_idx <- store_find_best_match(store, target_state)

# Convert to data.frame for debugging
df <- store_to_dataframe(store)

GPU acceleration

Optional GPU support via the ggmlR package (Vulkan backend). Install ggmlR separately; cayleyR works without it (CPU fallback).

# Check GPU availability
cayley_gpu_available()
cayley_gpu_status()

# Manhattan distance (GPU vs CPU)
calculate_differences(start_state, states_df, use_gpu = TRUE)

# Batch apply operations to many states at once
apply_operations_batch_gpu(states_matrix, c("1", "3", "2"), k = 4)

# Pairwise distance matrix
manhattan_distance_matrix_gpu(states1, states2)

Package functions

Basic Operations (C++):

• shift_left() / shift_right() — cyclic shifts with coordinate tracking
• shift_left_simple() / shift_right_simple() — simple cyclic shifts
• reverse_prefix() / reverse_prefix_simple() — reverse first k elements
• apply_operations() — apply sequence of operations

3x3x3 cube (pure R):

• cube3_moves — the eighteen face turns as sticker permutations
• cube3_move_codes / cube3_move_names() — the 1–18 numbering, and back to names
• cube3_identity() / cube3_is_solved() — the solved state, and the test for it
• cube3_apply() — apply a single move
• cube3_parse_moves() — read either spelling, return codes
• cube3_inverse_move() — invert a move
• cube3_scramble() — random scramble, never the same face twice running
• cube3_cycle() — unroll a word until it closes
• cube3_print() — unfolded net for the console

Sequences are handled by the group API — group_apply(), group_compose(), group_order(), group_inverse_seq() — which works on any group in the package, TopSpin included.

Cubes of any size

Every cube function in the package, and the sizes it actually accepts. The sizes are measured rather than read off the documentation: each function was called at n = 2 through 7 and the answer recorded. Any n means all six sizes worked.

Structure — the group and its geometry (all: any n):

Function	What it gives
cube_group()	the group of an n x n x n cube, 6n moves over 6n^2 stickers
cube_moves() / cube_move_names()	the generated move table, and its names
cube_layer_move()	one turn named by axis, layer and quarter turns
cube_identity()	the solved state, 1:(6n^2)
cube_is_colour_solved()	every face one colour, which slice turns make distinct from the identity
cube_orbits() / cube_pieces()	the orbits a size has, and which stickers each piece carries
cube_progress() / cube_pieces_home()	how much of each orbit is solved
cube_colours()	a state written as colours rather than positions
cube_wing_geometry_cpp()	where the wings of a size sit

Notation — reading and expanding words (all: any n):

Function	What it gives
cube_expand_move() / cube_expand_word()	Rw, 3R, x turned into single-layer moves at that size
cube_wide_move() / cube_wide_word()	the same, composed into one permutation
cube_expand_alg()	an algorithm string expanded
cube_word_order()	how many repetitions bring a word back to the start
cube_alg_table()	the OLL, PLL and layer-by-layer tables
cube_centre_positions()	the centre sticker of each face

Centres — derived from the size, not tabulated (all: any n):

Function	What it gives
cube_centre_structure()	every centre sticker: face, orbit and slot
cube_slice_map()	where a turn sends each centre, as (face, orbit, slot)
cube_centre_shots()	commutators that carry centres off one face and spare another
cube_central_moves()	the turns that rotate the whole cube — empty on an even cube
cube_centre_counts()	how many centres are home, per face, optionally per orbit

Santa-format interchange (all: any n):

cube_santa_group(), cube_santa_moves(), cube_santa_move_names(), cube_moves_santa(), cube_santa_perm(), cube_santa_state(), cube_santa_state_out(), cube_santa_path(), cube_santa_path_out() — converting states and paths to and from the Santa competition's conventions.

Learned solving (any n):

cube_adi_model(), cube_adi_train(), cube_adi_solve() — autodidactic iteration over any cube group, given ggmlR.

Tied to one size:

Function	Sizes	Why
cube_solve_cfop(), cube_solve_lbl(), cube_solve_m2(), cube_solve_old_pochmann(), cube_kociemba()	3 only	human and blindfolded methods written for a 54-sticker cube
cube_read_state(), cube_predicates(), cube_apply_word()	3 only	read and describe a 3x3x3
cube_solve4(), cube_solve4_cascade(), cube_solve_centres()	4 only	reduction built around four centres to a face
cube_is_reduced()	4 only	the 4x4x4 test for "now solvable as a 3x3x3"
cube_kociemba4(), cube_kociemba4_reduce(), and the _cpp phase helpers	4 only	the two-phase search over a 4x4x4's coordinates

The split is clean and worth stating plainly: the structure of a cube is universal, the methods that solve one are not. Anything that describes a cube — its moves, orbits, pieces, notation, centres — works at any size, because it is derived from the geometry. Anything that solves a cube is still written for the size it was written for. A 5x5x5 therefore has a full vocabulary and no solver.

Solving the 3x3x3:

• cube_solve_cfop() — cross, F2L by IDA*, OLL, PLL; the fewest moves and the only one that searches
• cube_solve_lbl() — layer by layer, the beginner's method
• cube_solve_old_pochmann() — blindfolded: one piece per conjugated PLL, plus the parity step
• cube_solve_m2() — blindfolded with the edges done by M2 instead, about two thirds the moves
• cube_kociemba() — the two-phase search: into the subgroup <U, D, L2, R2, F2, B2>, then to solved within it. A quarter of CFOP's moves, and the only solver here with a prune table. Short rather than shortest — phase 1 takes the first way in it finds. The search machinery follows twips (MPL-2.0)

Analysis:

• get_reachable_states() — full cycle analysis with state tracking
• get_reachable_states_light() — lightweight cycle detection
• find_best_random_combinations() — find best random sequences with flexible sort_by
• analyze_top_combinations() — analyze top operation sequences

StateStore (C++ backend):

• create_state_store() — create compact hash-indexed store
• store_add_from_df() — add states from data.frame
• store_analyze_combos() — analyze combos directly into store (no data.frame)
• store_find_intersections() — O(min(N,M)) hash intersection
• store_find_best_match() — Manhattan distance best match
• store_filter_middle() — filter middle steps per combo
• store_to_dataframe() — convert to data.frame for debugging
• store_reconstruct_path() — C++ path reconstruction through cycles
• store_lookup() — hash lookup by state vector
• store_get_state() / store_get_meta() — retrieve state and metadata by index

Pathfinding:

• bidirectional_bfs() — bidirectional BFS shortest path
• find_path_iterative() — Iterative Cycle Intersection (ICI) path solver (StateStore backend)
• find_path_bfs() — find path via BFS highways + iterative connector (auto direct vs hub)
• short_path_bfs() — shorten existing path via greedy BFS hopping
• human_algorithm() — human-style solver: grow a sorted run, finish the tail with derived cycle primitives
• sparse_bfs() — sparse BFS with hybrid hub/random selection
• reconstruct_bfs_path() — reconstruct path from sparse BFS result
• validate_and_simplify_path() — validate and simplify operation path
• invert_path() — reverse an operation path

GPU (optional, requires ggmlR):

• cayley_gpu_available() / cayley_gpu_init() / cayley_gpu_status() / cayley_gpu_free() — GPU management
• calculate_differences(..., use_gpu = TRUE) — Manhattan distance on GPU
• apply_operations_batch_gpu() — batch operations via matrix multiplication
• manhattan_distance_matrix_gpu() — pairwise distance matrix

Distance Metrics:

• manhattan_distance() — Manhattan distance between states
• breakpoint_distance() — breakpoint distance between states
• calculate_differences() — compute distances for all states in a table

Celestial Coordinates:

• convert_LRX_to_celestial() — map LRX operation counts to spherical coordinates
• calculate_angular_distance_z() — angular distance between two coordinate sets
• calculate_midpoint_z() — midpoint between two coordinate sets
• find_closest_to_coords() — find state closest to target coordinates

State Utilities:

• generate_state() / generate_unique_states_df() — random state generation
• select_unique() — deduplicate states by V-columns
• check_duplicates() — find states present in two tables
• find_combination_in_states() — find a specific state in results
• save_bridge_states() — save bridge states to CSV
• short_position() — simplify operation path
• convert_digits() — parse operation strings

Measured performance

Measured on a 12-core machine, k = 4, paths produced by human_algorithm_to(). Every figure below comes from a run of the scripts in inst/examples/; each shortened path is verified by applying it to the start state and comparing against the target.

Solving (inst/examples/benchmark_human_algorithm_to.R)

The ring-size cap of 63 is gone, so these sizes are reachable at all. Time grows close to linearly in n; the move count does not, because it depends on how the scramble happened to fall.

n	sec	raw	short	found
100	2.576	1340.3	1325.7	3/3
200	4.727	1614.3	1606.3	3/3
300	6.949	4144.3	4137.0	3/3
400	9.208	5290.7	5278.0	3/3
500	11.607	6589.0	6138.3	3/3
600	14.045	6445.3	6431.3	3/3
700	16.493	6140.3	6125.7	3/3
800	19.083	12717.0	12713.7	3/3
900	21.651	15540.3	15534.3	3/3
1000	24.266	8124.7	8108.0	3/3

3 runs per size, shortening via short_path_bfs(depth = 4).

Shortening (inst/examples/benchmark_cycle_shortcut.R)

cycle_shortcut() and short_path_bfs() hunt for the same thing by different means, and on these paths neither finds much. The honest summary is that short_path_bfs() is the better default up to a point, and that ranking the combos costs several times what it returns:

n	path	cycle_shortcut (ranked)	cycle_shortcut (no ranking)	short_path_bfs
100	978	0 saved, 7.2s	0 saved, 1.2s	0 saved, 0.5s
500	4248	6 saved, 131.8s	6 saved, 21.6s	10 saved, 19.7s (depth 6)
2000	31005	0 saved, 339.0s	0 saved, 57.7s	4 saved, 624.9s (depth 6)

Two things worth reading off this table. Ranking combos (sort_by) has to unroll every candidate to score it and bought nothing here — sort_by = NULL returned the same cuts five to six times faster. And the crossover is at n = 2000, where short_path_bfs() becomes the slower of the two by an order of magnitude while still being the only one that finds anything.

Cutting across cycles pays off on small rings and thins out as the state space grows: a random cycle leaving the path rarely meets it again when there is that much room to wander. See TODO for what this needs.

Examples

Scripts in inst/examples/, runnable with Rscript inst/examples/<name>.R. Each has a parameters block at the top; nothing needs editing to get a first run out of it.

Solvers and paths

Script	What it does
test_path.R	Integration run of find_path_iterative() (ICI) on a scrambled ring
test_bh_in_path.R	find_path_bfs() on a fixed 20-tile target, writing path and stats to CSV
test_bh_path_coords.R	Same path, plus celestial coordinates accumulated at every step
test_human_algorithm.R	The human-style solver: grow a sorted run, finish the tail with cycle primitives
test_human_navigation.R	Solving driven by phase 1 of the human algorithm instead of Manhattan distance, one direction only
test_sparse_bh.R	Sparse BFS with look-ahead and hybrid hub selection

Benchmarks

Script	What it measures
benchmark_human_algorithm_to.R	human_algorithm_to() sweeping ring size: time, raw and shortened move counts
benchmark_cycle_shortcut.R	cycle_shortcut() against short_path_bfs(), with and without combo ranking
benchmark_human_nav.R	Three ways of solving the same states — navigation plus search, versus the human algorithm
benchmark_n_size.R	Difficulty as the ring grows, n_moves held fixed
benchmark_n_moves.R	Difficulty as the scramble lengthens, n held fixed
benchmark_sort_by.R	Which sort_by strategy serves find_path_iterative() best
benchmark_gpu_vs_cpu.R	store_analyze_combos() on CPU/C++ against the GPU path

Graph structure

Script	What it shows
graph_diameter.R	Graph diameter and the state pairs that realise it
demo_graph_celestial.R	The whole Cayley graph plotted in celestial coordinates
demo_graph_spectral.R	The same graph in spectral coordinates, which separate states celestial ones collapse
demo_graph_spectral_nobfs.R	Spectral layout without a full BFS, for rings too large to enumerate
coord_diagnostics.R	Whether a coordinate actually predicts graph distance, over arbitrary pairs rather than pairs involving the identity
probe_human_table.R	What drives the cost of building the finish table — k, as it turns out, not the ring size

Dependencies

• Rcpp — C++ implementations of core operations (required). The cube side (cube3_*) is pure R and needs none of it.
• data.table (optional) — faster rbindlist when available
• ggmlR (optional) — GPU acceleration via Vulkan

License

MIT