The package started with TopSpin,
but nothing in its search code needs to know which puzzle it is solving.
All it needs is the group: how long a state is, which
moves there are, and what each move does. A perm_group
object holds exactly that. You pass it to a function through
group =, so the same code works on TopSpin, on a Rubik’s
cube, or on a puzzle you describe yourself.
tg <- topspin_group(8, k = 4, moves = c("L", "R", "X"))
tg
#> <perm_group> topspin(n=8, k=4)
#> state length: 8
#> moves (3): L R X
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'A TopSpin ring of 8 tiles has three moves. X reverses
the first k = 4 tiles, and the group fixes k
when you build it. A 3x3x3 cube has 54 stickers and 18 quarter turns,
slices included.
TopSpin’s moves are named "1", "2",
"3" by default. Pass moves = c("L", "R", "X")
if you want to write words with letters, as in this vignette.
A state is an integer vector, and the solved state is
1:n. A word can be a vector of move names or one string
with spaces:
group_apply(tg, group_identity(tg), "L L X")
#> [1] 6 5 4 3 7 8 1 2
s <- group_apply(cg, group_identity(cg), "R U R' U'")
sum(s != group_identity(cg)) # stickers out of place
#> [1] 18group_inverse_seq() writes the word that undoes a given
one. You never have to declare inverses: the group works them out from
the permutations.
How many times must a word be repeated to return to the start? The
answer does not depend on the starting state, and
group_order() computes it:
group_order(cg, "R") # a quarter turn: 4
#> [1] 4
group_order(cg, "R U R' U'") # the "sexy move": 6
#> [1] 6
group_order(cg, "R U") # 105
#> [1] 105
group_order(tg, "L") # going once round the ring
#> [1] 8Cycles like these drive the iterative solver: one word repeated many times sweeps through a long cycle of states.
perm_group() builds a group from a named list of
permutations. Each permutation is read as
new[i] <- state[perm[i]], i.e. position i
takes its value from position perm[i]. No C++ is
needed.
Here is a toy puzzle on five points. It has a rotation
a, its inverse a', and a swap of the first two
points b:
toy <- perm_group(list(
a = c(2L, 3L, 4L, 5L, 1L),
"a'" = c(5L, 1L, 2L, 3L, 4L),
b = c(2L, 1L, 3L, 4L, 5L)
), name = "toy")
toy
#> <perm_group> toy
#> state length: 5
#> moves (3): a a' b
group_apply(toy, 1:5, "a a b")
#> [1] 4 3 5 1 2
group_inverse_seq(toy, "a a b")
#> [1] "b" "a'" "a'"
group_order(toy, "a b")
#> [1] 4Everything above works on this group straight away, and so does every
function in the package that takes group =.
generate_state() takes a group too. Given one, it only
returns states the puzzle can actually reach, rather than an arbitrary
permutation of 54 numbers:
You can build a cube group that uses only some of the moves. Here the middle slice turns alone:
m_only <- cube_group(3, moves = c("M", "M'"))
m_only
#> <perm_group> cube3x3x3
#> state length: 54
#> moves (2): M M'
generate_state(group = m_only, n_moves = 5)
#> [1] 1 53 3 4 50 6 7 47 9 10 11 12 13 14 15 16 17 18 19 2 21 22 5 24 25
#> [26] 8 27 28 20 30 31 23 33 34 26 36 37 38 39 40 41 42 43 44 45 46 35 48 49 32
#> [51] 51 52 29 54