# 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.