The Rubik’s Cube

The package handles a Rubik’s cube the same way it handles TopSpin. A state is an integer vector, a move permutes it, and the cube is a perm_group (see vignette("permutation-groups")). This vignette covers how the cube is written down and the five 3x3x3 solvers.

Stickers and moves

A cube of side n has 6n^2 stickers, so a 3x3x3 has 54. They are numbered face by face in the order U R F D L B. Within a face the order is left to right, top to bottom, as seen from outside. The solved cube is 1:54.

cg <- cube_group(3)
cg
#> <perm_group> cube3x3x3
#>   state length: 54
#>   moves (18): U U' R R' F F' D D' L L' B B' M M' E E' S S'

There are 18 moves: the six faces and the three middle slices M, E, S, each in two directions. Half turns are not separate moves: U2 is written "U U". So every move count in the package is in quarter turns.

s <- group_apply(cg, cube_identity(3), "R U U F'")
s[1:9]                 # the U face: which sticker sits in each place
#> [1] 27  8  7 24  5  4 37 17 18

Colours

A sticker’s colour is the face it started on. cube_colours() turns a state into colours 0–5, and that is how a cube looks from outside:

face_U <- function(state) matrix(cube_colours(state)[1:9], 3, byrow = TRUE)
face_U(cube_identity(3))
#>      [,1] [,2] [,3]
#> [1,]    0    0    0
#> [2,]    0    0    0
#> [3,]    0    0    0
face_U(group_apply(cg, cube_identity(3), "R"))
#>      [,1] [,2] [,3]
#> [1,]    0    0    2
#> [2,]    0    0    2
#> [3,]    0    0    2

With slices among the moves, the centres move too. Turning all three layers of one axis turns the whole cube in space. It still looks solved, but its stickers are no longer 1:54. cube_is_colour_solved() checks the colours, not the positions:

s <- group_apply(cg, cube_identity(3), "R M' L'")
cube_is_colour_solved(s)
#> [1] TRUE
identical(s, cube_identity(3))
#> [1] FALSE

A scramble

generate_state() with a cube group gives a state a real cube can reach:

set.seed(42)
scramble <- generate_state(group = cg, n_moves = 25)
face_U(scramble)
#>      [,1] [,2] [,3]
#> [1,]    5    4    5
#> [2,]    5    0    1
#> [3,]    2    2    3

Five solvers

All five take a 54-sticker state and return a list with the same shape: path is the moves, found says whether the cube ended up solved.

Function Method
cube_solve_lbl() layer by layer, the beginner’s method
cube_solve_cfop() CFOP: cross, F2L, OLL, PLL
cube_solve_old_pochmann() blindfolded, one piece at a time
cube_solve_m2() blindfolded, M2 for the edges
cube_kociemba() two-phase search after Kociemba

The first four are human methods: they place pieces by rule or from a table, as a person would. Kociemba’s method searches instead, and finds much shorter solutions.

solvers <- list(
  lbl           = cube_solve_lbl,
  cfop          = cube_solve_cfop,
  old_pochmann  = cube_solve_old_pochmann,
  m2            = cube_solve_m2,
  kociemba      = cube_kociemba
)

res <- lapply(solvers, function(f) f(scramble))

data.frame(
  found  = sapply(res, `[[`, "found"),
  moves  = sapply(res, function(r) length(r$path))
)
#>              found moves
#> lbl           TRUE   173
#> cfop          TRUE    87
#> old_pochmann  TRUE   463
#> m2            TRUE   321
#> kociemba      TRUE    33

Every path can be checked by applying it to the scramble:

sapply(res, function(r) cube_is_colour_solved(group_apply(cg, scramble, r$path)))
#>          lbl         cfop old_pochmann           m2     kociemba 
#>         TRUE         TRUE         TRUE         TRUE         TRUE

We check colours rather than positions because M2 can leave the centres turned among themselves. The cube is still solved by any reasonable reading.

Stages

The human methods also report the stages they went through, with the number of moves spent on each:

res$cfop$stages
#>            name                 detail n_moves
#> 1  cross edge 1                 insert       7
#> 2  cross edge 2         insert flipped       3
#> 3  cross edge 3         insert flipped       4
#> 4  cross edge 4                 insert       2
#> 5    F2L slot 1                lift FL       3
#> 6    F2L slot 1  F2L 19 (pair on side)      11
#> 7    F2L slot 2 F2L 33 (edge in place)       9
#> 8    F2L slot 4  F2L 21 (pair on side)      11
#> 9           OLL           OLL 18 (Dot)      21
#> 10          PLL                      E      16

The CFOP solution is long even though each stage is solved optimally. A stage that is shortest on its own usually leaves the next stage worse off.

Kociemba

Kociemba’s method works in two phases. Phase 1 brings the cube into the subgroup <U, D, L2, R2, F2, B2>, which has about 20 million states. Phase 2 solves it inside that subgroup. The solver takes the first phase-1 solution it finds, so the result is short but not the shortest possible.

The prune tables grow on demand. cube_kociemba_init() builds them in advance, so the cost is not paid during the first solve. cube_kociemba_report() shows what each phase did. When found is FALSE, the report tells you whether there was no solution or the node budget ran out:

cube_kociemba_report()
#> $phase1
#> [1] "found"
#> 
#> $phase1_nodes
#> [1] 53561
#> 
#> $phase2
#> [1] "found"
#> 
#> $phase2_nodes
#> [1] 36065

Other sizes

cube_group(n) works for any n >= 2, with the same rules: 6n moves, 6n^2 stickers. A 4x4x4 has two inner layers per axis. They have no standard letters, so they are written as axis and index:

cube_move_names(2)
#>  [1] "U"  "U'" "R"  "R'" "F"  "F'" "D"  "D'" "L"  "L'" "B"  "B'"
cube_move_names(4)
#>  [1] "U"   "U'"  "R"   "R'"  "F"   "F'"  "D"   "D'"  "L"   "L'"  "B"   "B'" 
#> [13] "1x"  "1x'" "1y"  "1y'" "1z"  "1z'" "2x"  "2x'" "2y"  "2y'" "2z"  "2z'"

The 4x4x4 solvers are covered in their own vignette.