# How does scramble algorithm work?



## meowmeowmeow (Sep 22, 2017)

I'm making an timer app for iOS, but I need to understand how the scrambler alrogithm (e.g. Tnoodle) works before I can implement it into my timer.

Can anyone explain to me how they work?


----------



## xyzzy (Sep 22, 2017)

If you have half an hour to spare:





tl;dw: For the "easy" puzzles, you create a random state, solve that, and then return the inverse of the solution; for the "hard" puzzles, you directly generate a bunch of random moves.

The easiest route is probably to plug the scramble generators from other programs.


----------



## Bruce MacKenzie (Sep 22, 2017)

This is a bit of a "nit pick", but there is no reason for inverting the solution. If a position is statistically random its inverse will be random as well.


----------



## shadowslice e (Sep 23, 2017)

If you want to know about 2-phase algorithms the wiki has a fairly good explanation under kociemba's algorithm


----------



## Bruce MacKenzie (Sep 23, 2017)

Here is some code that I use to generate random 3x3x3 cube states. It is
written in Objective C which you may be familiar with if you're working in iOS.
Everything is fairly generic until the end where I translate the position and
orientation info into my working cube representation. 
(This editor strips out the tabs. I hope this isn't too hard to read.)
*
*
*// Generate a Random Cube State*
*// The cubies are placed at random positions *
*// and orientations within the restrictions*
*// of parity.*
*
enum RM_Cubicle { UF, UR, UB, UL, DF, DR, DB, DL, FR, FL, BR, BL, UFR, URB, UBL, ULF, DRF, DFL, DLB, DBR};
typedef enum RM_Cubicle RM_Cubicle;

enum { RM_TWIST_NO = 0 , RM_TWIST_CW , RM_TWIST_CCW };

-(NSData *)randomState
{
uint8 state[20];
uint64 rNumber;
uint8 perm[20],
orient[20],
offset[20],
twist[3] = { 0 , 0 , 0 };
int i, n, p,
range,
cubie;
BOOL done;

for( i = 0 ; i < 20 ; i++ )
perm[ i ] = UINT8_MAX;
*
_* //assign the edges random orientations: 0 thru 1, 0 = no flip*
* 
rNumber = [self random64]; //64 random bits from random device

for( cubie = UF , orient[BL] = 0 ; cubie < BL ; cubie++ )
{
orient[cubie] = rNumber & 1;
rNumber >>= 1;

orient[BL] ^= orient[cubie]; //the orientation of the last cubie is constrained
}

//assign the corners random orientations: 0 thru 2, 

for( cubie = UFR ; cubie < DBR ; cubie++ )
{
orient[cubie] = rNumber % 3;
rNumber /= 3;

twist[ orient[cubie] ]++;
}
*
* //Balance the twist with the DBR cubie*
* 
twist[RM_TWIST_CW] %= 3;
twist[RM_TWIST_CCW] %= 3;

orient[DBR] = RM_TWIST_NO;

if( twist[RM_TWIST_CW] > twist[RM_TWIST_CCW] )
{
twist[RM_TWIST_CW] -= twist[RM_TWIST_CCW];
if( twist[RM_TWIST_CW] == 1 )
orient[DBR] = RM_TWIST_CCW;
else
orient[DBR] = RM_TWIST_CW;
}
else
{
if( twist[RM_TWIST_CCW] > twist[RM_TWIST_CW] )
{
twist[RM_TWIST_CCW] -= twist[RM_TWIST_CW];
if( twist[RM_TWIST_CCW] == 1 )
orient[DBR] = RM_TWIST_CW;
else
orient[DBR] = RM_TWIST_CCW;
}
}

//generate random offsets in a list of unoccupied cubicles

rNumber = [self random64];

for( cubie = UF , range = 12 ; cubie < UFR ; cubie++ , range-- )
{
offset[cubie] = rNumber % range; // 0 thru 11 , 0 thru 10 , 0 thru 9 ...
rNumber /= range;
}

rNumber = [self random64];

for( cubie = UFR , range = 8 ; cubie < 20 ; cubie++ , range-- )
{
offset[cubie] = rNumber % range;
rNumber /= range;
}

//place the cubies at random positions based on the above offsets

for( cubie = 0 ; cubie < 20 ; cubie++)
{
done = NO;
i = 0;
range = 0;
do
{
if( perm == UINT8_MAX )
 {
 if( range == offset[cubie] )
 {
 perm = cubie;
 done = YES;
 }
 range++;
 }
 i++;
 }while( done == NO );
 }
*
* // rectify the parity if necessary*

* // Count inversions** 
for( p = 0 , i = 0 ; i < 19 ; i++ )
for( n = i + 1 ; n < 20 ; n ++ )
if( perm > perm[n] )
 p ^= 1;

 if( p == 1 )
 {
 i = perm[19];
 perm[19] = perm[18];
 perm[18] = i;
 }
*
* //translate the permutation and orientations to a list of geometric transforms*
* //to apply to the cubies*
* 
for(cubie = 0 ; cubie < 20 ; cubie++ )
state[cubie] = [self symTagToPlaceCubie: cubie
inCubicle: perm[cubie]
withOrientation: orient[cubie] ];

return [NSData dataWithBytes: state length: sizeof(CM_SYMTAG [20])];
}*_


----------



## xyzzy (Sep 23, 2017)

Bruce MacKenzie said:


> This is a bit of a "nit pick", but there is no reason for inverting the solution. If a position is statistically random its inverse will be random as well.



4×4×4 states don't form a group, so you can't meaningfully speak of an inverse. Likewise for square-1.


----------



## Bruce MacKenzie (Sep 23, 2017)

xyzzy said:


> 4×4×4 states don't form a group, so you can't meaningfully speak of an inverse. Likewise for square-1.


I'm not sure that that is true. The 4x4x4 states certainly may be mapped to a permutation group. In the 4x4x4 cube you have the complication that the turn set allows each cube state to be produced in any of 24 orientations. This is shared by the 2 x 2 x 2 cube, the void cube, and the 3 x 3 x 3 cube if middle slice turns are included. This is resolved in each case by defining a preferred orientation. In the 3x3x3 cube one defines a preferred orientation of the center cubies. In the 2x2x2, the void cube and the 4x4x4 cube one defines a preferred orientation by one of the corner cubies. The preferred orientation is that which places the DLB cubie, say, in its starting position and orientation. Using these conventions the states of the puzzle do form a well behaved mathematical group.


I'm not familiar with Square-1 but I would be surprised if the puzzle states could not be mapped to a permutation group. It could be like the 15-Puzzle which can be mapped to a permutation group but where inverse move sequences are not in general valid. In that case one couldn't physically apply a solution sequence to the solved puzzle and one would need to invert that move sequence.

Anyway, there is nothing wrong with inverting the solution sequence. It's just not necessary in most cases.


----------



## xyzzy (Sep 23, 2017)

Bruce MacKenzie said:


> The 4x4x4 states certainly may be mapped to a permutation group.


Only if you have a supercube. On a normal cube, the centres are not distinguishable, so the states actually biject to a quotient of the permutation group (and this isn't a group, because the subgroup being modded out isn't normal). Centre/corner orientation is a red herring.



Bruce MacKenzie said:


> Anyway, there is nothing wrong with inverting the solution sequence. It's just not necessary in most cases.


I agree! I just didn't want to complicate my post with "oh except for these cases where you do need to invert the solution; read these two chapters of Dummit & Foote so you have the mathematical background to understand why sometimes you can skip inverting". My kilominx and Redi Cube random-state scramblers return the solution as is, rather than inverting it, but then again I'm pretty sure I know what I'm doing. (There are further reasons for not inverting the solution, but those are specific to my scramblers and don't apply everywhere. I wrote a bit about this elsewhere on the forum.)


----------



## Bruce MacKenzie (Sep 23, 2017)

xyzzy said:


> Only if you have a supercube. On a normal cube, the centres are not distinguishable, so the states actually biject to a quotient of the permutation group (and this isn't a group, because the subgroup being modded out isn't normal). Centre/corner orientation is a red herring.



I don't follow the point you are making here. I repeat that the states of the 4x4x4 can indeed be mapped to a permutation group and the inverse is well defined. Now if you take a non-optimal solution sequence for a randomly selected 4x4x4 cube state and apply it to a pristene cube you will not in general get the inverse of that state but rather a rotational conjugate of the inverse. It makes no difference. It will still be a randomly selected cube state.


----------



## Bruce MacKenzie (Sep 23, 2017)

xyzzy said:


> If you have half an hour to spare:
> 
> 
> 
> ...



I viewed the video and have some thoughts:

In order to model the 4x4x4 cube as a mathematical group one must define a preferred orientation. Usually one defines the preferred orientation as that which places the DLB cubie properly oriented in the DLB slot. The standard turn set for the 4x4x4 moves the DLB cubie around. In order for turn sequences to combine like elements of the group one has to tack on a whole cube rotation to end of the sequence--the whole cube rotation which will return the cube to the preferred orientation. The inverse turn sequence must also invert this whole cube rotation. First one must apply the inverse whole cube rotation and then apply the inverse turn sequence. This will return the cube to the original state. So, if the standard rules for 4x4x4 don't take this into account the cube is not returned to the originally selected random cube state but rather to a rotational conjugate of that state. Which is OK. It doesn't introduce any bias.


----------



## xyzzy (Sep 23, 2017)

Bruce MacKenzie said:


> I don't follow the point you are making here. I repeat that the states of the 4x4x4 can indeed be mapped to a permutation group and the inverse is well defined. Now if you take a non-optimal solution sequence for a randomly selected 4x4x4 cube state and apply it to a pristene cube you will not in general get the inverse of that state but rather a rotational conjugate of the inverse. It makes no difference. It will still be a randomly selected cube state.


Yes, you have a map, but the choice of map is extremely nonunique (something like $$24^{6\cdot\frac{24!}{(4!)^6}}\approx10^{10^{16}}$$ choices) and none of these choices give a group homomorphism.

A 4×4×4 has way too many cases to do a demo with. Consider a 2×2×2 restricted to R2, F2 and U moves, and peel off every sticker other than the U and D ones. This puzzle has a total of 35 states, small enough to enumerate and optimally solve by hand in a few minutes. Let's say we pick this set of optimal solutions (not unique!):


Spoiler



"" (empty move sequence)
U F2 U' F2
F2 U' F2
U' F2 U' F2
R2 U F2
U R2 U' R2
R2 U' R2
U' R2 U' R2
F2 U R2
U' R2 U R2
F2 U' R2
U R2 U R2
R2 U R2
U R2 U' F2
R2 U' F2
U' R2 U' F2
F2 U R2
R2
U R2
U2 R2
U' R2
F2
U F2
U2 F2
U' F2
R2 U' R2 U' R2
R2 U R2 U R2
F2 U F2 U F2
F2 U' F2 U' F2
R2 U F2 U R2
F2 U' R2 U' F2
R2 U' F2 U' F2
F2 U R2 U R2
R2 U2 F2
U R2 U2 F2



By your logic, we can pick a random state, solve it, and return the solution directly. This is equivalent to picking a scramble sequence out of the 35 choices above uniformly. However, you have this case showing up 4/35 of the time and this case showing up never, so this process clearly doesn't lead to a uniform distribution.

It's the same issue on a 4×4×4 (and bigger cubes): you can't easily guarantee that the distribution over all the states is uniform if you don't invert the solution, simply because you have identical pieces.

(Optimal or suboptimal is, again, a red herring. The group doesn't care about how many moves you use. Consider Uw2 Rw2 U2 Rw2 R2 U2 Rw2 Uw2 and Rw2 F2 U2 Rw2 R2 U2 F2 Rw2, which result in the same pattern and are optimal in OBTM, but permute the centres differently.)


----------



## Bruce MacKenzie (Sep 23, 2017)

xyzzy said:


> Yes, you have a map, but the choice of map is extremely nonunique (something like $$24^{6\cdot\frac{24!}{(4!)^6}}\approx10^{10^{16}}$$ choices) and none of these choices give a group homomorphism.
> 
> A 4×4×4 has way too many cases to do a demo with. Consider a 2×2×2 restricted to R2, F2 and U moves, and peel off every sticker other than the U and D ones. This puzzle has a total of 35 states, small enough to enumerate and optimally solve by hand in a few minutes. Let's say we pick this set of optimal solutions (not unique!):
> 
> ...



Ok, I get you now. Good example. When you have identical pieces you're not dealing with a mathematical group but rather a coset space of a mathematical group. Inverses are not defined for coset spaces unless you're dealing with cosets of a normal subgroup. The 4x4x4 does have identical pieces (a fact I hadn't considered) so the inverses are not well defined. 

Good discussion. I've learned something.


----------



## JustinTimeCuber (Sep 23, 2017)

4x4 isn't a group but it behaves a lot like a group.

4x4 positions *do* have inverses, just not unique inverses.

also if you have a truly random state its *inverse* is random.


----------



## xyzzy (Sep 24, 2017)

JustinTimeCuber said:


> 4x4 positions *do* have inverses, just not unique inverses.
> 
> also if you have a truly random state its *inverse* is random.



What exactly do you mean by "inverse" anyway? The word has a precise meaning in a mathematical context, but the set of 4×4×4 states is not, _a priori_, a mathematical object in which the notion of "inverse" is even defined. (This statement also holds for the 2×2×2 and 3×3×3, where we _do_ have a group structure and hence the notion of "inverse states", but the fact that they have a group structure is not obvious and requires proof. Exercise for the reader: prove this.)

Meanwhile, there's an obvious "inverse" operation when we talk about _move sequences_ rather than _the result of the move sequence applied to a solved cube_, because the set of move sequences behaves exactly like a free group.


----------



## JustinTimeCuber (Sep 24, 2017)

xyzzy said:


> What exactly do you mean by "inverse" anyway? The word has a precise meaning in a mathematical context, but the set of 4×4×4 states is not, _a priori_, a mathematical object in which the notion of "inverse" is even defined. (This statement also holds for the 2×2×2 and 3×3×3, where we _do_ have a group structure and hence the notion of "inverse states", but the fact that they have a group structure is not obvious and requires proof. Exercise for the reader: prove this.)
> 
> Meanwhile, there's an obvious "inverse" operation when we talk about _move sequences_ rather than _the result of the move sequence applied to a solved cube_, because the set of move sequences behaves exactly like a free group.


Any sequence of moves on a 4x4 has the effect of certain swaps and cycles. Just do those swaps and cycles in reverse, and that's the inverse, right?


----------



## Bruce MacKenzie (Sep 24, 2017)

JustinTimeCuber said:


> 4x4 isn't a group but it behaves a lot like a group.
> 
> 4x4 positions *do* have inverses, just not unique inverses.
> 
> also if you have a truly random state its *inverse* is random.




Ok, let's think this through.

There is a mathematical group, G, composed of all the arrangements the 4x4x4 puzzle pieces may be placed in by combinations of the puzzle moves. The group G has a subgroup, S, composed of all the even parity arrangements which may be produced by taking the solved puzzle and swapping identical puzzle pieces. There are 2^11 members of this subgroup. They are all indistinguishable and all represent a solved cube.


The distinct states of the 4x4x4 puzzle may then be mapped by the left cosets of the subgroup, S:

g * S , where g is any member of the parent group.

All the members of a coset are indistinguishable and represent the same puzzle position.

A member of a coset, g * s1, will have an inverse, s1' * g'. What happens if one applies this inverse to a second member of the same coset, g * s2?

g * s2 * s1' * g'

Since S is a mathematical group this may be simplified to:

g * s3 * g'

The question arises, will a conjugate of a member of S by an arbitrary element of the parent group give another member of S? The answer is no. s3 * g' is going to swap around front-up cubies with right-back cubies or whatever and the conjugate is not going to be a solved cube. So, one can define an inverse for any particular member of the parent group but not for the elements of a coset on the whole.

Addendum:

In the above I right multiplied by the inverse. If you left multiply you get:


s1' * g' * g * s2 =
s1' * s2 =
s3

So, if you solve a puzzle position that turn sequence will convert any member of that position's coset to a member of the solved coset. So in that sense inverses in a coset space do perform like inverses in a mathematical group. But in a group inverses commute:

q * q' = q' * q = E

In a coset space, as I showed above, that is not the case. A consequence of that is that my contention that one doesn't need to invert the solution sequence for a random scramble is wrong, as the estimable xyzzy showed with his example above. So take to heart the caveat: don't assume a coset space has the same properties as a mathematical group. If you do it will rise up and bite you.


----------



## Bruce MacKenzie (Sep 24, 2017)

xyzzy said:


> What exactly do you mean by "inverse" anyway? The word has a precise meaning in a mathematical context, but the set of 4×4×4 states is not, _a priori_, a mathematical object in which the notion of "inverse" is even defined. (This statement also holds for the 2×2×2 and 3×3×3, where we _do_ have a group structure and hence the notion of "inverse states", but the fact that they have a group structure is not obvious and requires proof. Exercise for the reader: prove this.)
> 
> Meanwhile, there's an obvious "inverse" operation when we talk about _move sequences_ rather than _the result of the move sequence applied to a solved cube_, because the set of move sequences behaves exactly like a free group.



In the 3 x 3 x 3 group modeled on the qtm metric or the ftm turn sequences do compose like group elements. The product of two group elements may be found by con-catenating generator turn sequences. The inverse is found by inverting the turn sequence. With the stm this is not the case since the middle slice turns rotate the center cubies out of their default positions. In order for stm turn sequences to compose as group elements they must be composed with whole cube rotations which return the cube to the default orientation after the moves.

If one models the 2 x 2 x 2 cube using the ( U , F , R ) turn set then turn sequences compose like group elements. If ( D , B , L ) turns are added to the turn set then like for the stm, turn sequences must be composed with a whole cube rotation to keep the cube in the default orientation. Then the turn sequences will compose like group elements.


----------



## xyzzy (Sep 24, 2017)

This is getting off topic lol.



JustinTimeCuber said:


> Any sequence of moves on a 4x4 has the effect of certain swaps and cycles. Just do those swaps and cycles in reverse, and that's the inverse, right?



That's the inverse of the sequence of moves, not the inverse of a cube state. The distinction between the _state_/_position_ of a twisty puzzle and the _move sequence_ to get to the state is what I'm trying to get at.

If you were to treat the puzzle's state as being the set of _all_ move sequences leading to it, you lose the essential properties of a group: that composition and inverse are well defined (i.e. single-valued). If you're fine with composition and inverse being multi-valued, then almost every operation you do causes the number of states you have to consider to grow exponentially. To emphasise: this isn't wrong _per se_, but it's definitely useless for computational purposes.


----------



## JustinTimeCuber (Sep 24, 2017)

xyzzy said:


> This is getting off topic lol.
> 
> 
> 
> ...


But can't you just consider the effect of the move sequences instead of the infinite set of sequences producing that effect?


----------



## xyzzy (Sep 24, 2017)

JustinTimeCuber said:


> But can't you just consider the effect of the move sequences instead of the infinite set of sequences producing that effect?



That gives you a permutation, not a state.


----------



## JustinTimeCuber (Sep 24, 2017)

xyzzy said:


> That gives you a permutation, not a state.


What's the difference in the context of a 4x4?


----------



## shadowslice e (Sep 24, 2017)

JustinTimeCuber said:


> What's the difference in the context of a 4x4?


You have indistinguishable pieces in a state but not a permutation


----------

