Message #4093
From: Andy F <legomany3448@gmail.com>
Subject: ClojureScript scrambler and some ideas about a near-optimal solver (plus "Fourtega" variant and my solve video)
Date: Wed, 01 Aug 2018 00:49:54 -0400
Hello again!
I have been hard at work the last several days creating my scrambler
<https://github.com/HactarCE/2x2x2x2-Scrambler> (much thanks to
pentaquark394 for the original Python script!), solution video
<https://youtu.be/Fd9NUaO5AYo>, and solution explanation
<https://docs.google.com/document/d/1vNc6bs3fl-XJ50Q96wOvy-grfpBVy_wmv9Ed_CLUqt0/edit?usp=sharing>.
(If anyone is planning on using my Clojure code, feel free, but be aware
that I may change the piece order soon.)
I agree with Marc that a compilation of useful algorithms is an excellent
idea; perhaps a wiki page <http://wiki.superliminal.com/wiki/2x2x2x2> may
be in order?
Now on the subject of scramblers …
The ideal scrambler for any puzzle would generate a random solvable state
and produce the optimal sequence of moves to arrive at this state.
Generating the "optimal" move sequence is rarely practical, so most 3^3
scramblers simply find a near-optimal sequence of moves using Kociemba’s
2-stage algorithm <http://kociemba.org/math/imptwophase.htm> or similar
<https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik’s_Cube>, which
is still usually around 20 moves. I don’t think there’s been much research
into this problem on the 2^4, so I’ll throw some numbers here just to get
some Fermi estimates. I should probably preface this by saying that I am by
no means an expert in combinatorics or optimal cube solving, and that I am
probably glossing over a numerous details that matter more than
easy-to-compute numbers, but I want to get some conversation started about
this.
2x2x2 states
7! * 3^6 = 3.67416e+6
3x3x3 states
8! * 3^7 * 12! * 2^11 / 2 = 4.325200327449e+19
4x4x4 states
8! * 3^7 * 24!^2 / 24^7 = 7.4011968415649e+45
2x2x2x2 states
s24 = 15! / 2 * 12^15 / 3 = 3.3578945333849e+27
Taking one piece as completely solved, there are 15 pieces to permute,
divided by 2 two for permutation parity, and 15 pieces to orient (12
orientations each), divided by 3 for corner twist parity
I think the 2^4 is most comparable to the 3^3 in terms of search space, but
even then it has nearly 10^8 times as many states.
Kociemba’s algorithm consists of two steps: orientation (reduction from <U
D R L F B> to <U D R2 L2 F2 B2>) and permutation (solving the puzzle using
<U D R2 L2 F2 B2>). These numbers give a rough estimate of the search space
involved with these steps, so any 2^4 algorithm should aim for similar
numbers in each stage.
Kociemba 3^3 stage 1 cases
3^7 * 2^11 = 4.478976e+6
Kociemba 3^3 stage 2 cases
8! * 12! / 2 = 9.656672256e+12
There’s no way to adapt this algorithm directly to the 2^4 without having
an unreasonably large search space. Instead, I’ve come up with an outline
for a 3-stage method as follows:
- Orient U/D stickers (in vertical orientation)
- Orient and separate I/O stickers
- Permute all pieces
This produces some quite reasonable-looking (using Kociemba’s stages as a
baseline) case counts.
Stage 1 cases
4^15 = 1.073741824e+9
Taking one piece as solved, there are 15 pieces to orient; we only care
about the position of the sticker that belongs on U/D, and there are four
places this could be
Stage 2 cases
3^14 * (15! / 8! / 8!) = 3.847300689375e+9
Taking one piece as solved, there are 15 pieces to orient, divided by 3
for corner twist parity, and 15 pieces to permute, but divide by 8! for I
and 8! for O since we don’t care about permutation within the layer
Stage 3 cases
7! * 8! / 2 = 1.6257024e+8
Taking one piece as solved, there are 7 pieces to permute on the I layer
and 8 pieces to permute on the O layer, divided by 2 for permutation parity
This is basically the PBBL step that I’ve proposed elsewhere – the
number here does not accounting for any symmetric cases, of course
Besides producing eerily even case counts (I’m not sure how well these
correspond to the average time or move count required to solve the step), I
chose these steps based on the move subsets they permit. Because the
primary purpose of this is to produce easy-to-execute scramble sequences,
I’ve only included certain easy-to-execute moves:
Stage 1:
{UD}[{xyz}{123}] - 18
U[U{123}] - 3
D[D{123}] - 3
{RLFB}2 - 4
vertical restack - 1
= 29 moves
Stage 2:
{UD}[{xyz}{123}] - 18
U[U{123}] - 3
D[D{123}] - 3
{RLFB}2 - 4
= 28 moves
Stage 3:
{UD}[y{123}] - 6
{UD}[{xz}2] - 4
U[U{123}] - 3
D[D{123}] - 3
{RLFB}2 - 4
= 20 moves
Note that I’ve included some moves, such as U[U], that toggle permutation
parity. This is intentional; my primary purpose here is not necessarily to
create a random-state *solver*, but a random-state *scrambler*. A
random-state scrambler that is guaranteed to produce a valid state needs
not worry about performing parity-violating sequences, as long as the whole
scramble preserves parity. With this taken into account, the number of
cases for stage 3 should really be 7! * 8! = 2.032128e+8, which is still
fine.
Note that in stage 2, only the restacking move is disallowed (which makes
sense since now the "frame" of the puzzle would be fixed), and in stage 3
the set <U<x z> D<x z>> has been reduced to <U<x2 z2> D<x2 z2>>, turning
the puzzle into what are effectively two PBL-ready 2^3 puzzles that happen
to be entangled such that a move on one must be accompanied by a move on
the other in the same direction.
I’m curious to hear other ideas about this, and whether anyone would be
willing to try writing such a solver (bonus points if it’s in Clojure 😉)
since doing this efficiently goes quite beyond my current CS knowledge,
though I’d be willing to give it a shot anyway.
- Andy
P.S. All of my future emails will be sent from my ajfarkas12 address rather
than legomany3448.