• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

How does scramble algorithm work?

meowmeowmeow

Member
Joined
Mar 17, 2016
Messages
6
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

Member
Joined
Dec 24, 2015
Messages
2,876
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.
 
Joined
Sep 3, 2017
Messages
105
Location
USA
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.
 
Joined
Sep 3, 2017
Messages
105
Location
USA
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])];
}
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,876
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.
 
Joined
Sep 3, 2017
Messages
105
Location
USA
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

Member
Joined
Dec 24, 2015
Messages
2,876
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.

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.)
 
Joined
Sep 3, 2017
Messages
105
Location
USA
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.
 
Joined
Sep 3, 2017
Messages
105
Location
USA
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.

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

Member
Joined
Dec 24, 2015
Messages
2,876
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!):
"" (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.)
 
Joined
Sep 3, 2017
Messages
105
Location
USA
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!):
"" (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.)

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.
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,876
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.
 
Joined
Aug 16, 2014
Messages
2,987
Location
Webster Groves, MO
WCA
2013BARK01
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?
 
Joined
Sep 3, 2017
Messages
105
Location
USA
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.
 
Last edited:
Joined
Sep 3, 2017
Messages
105
Location
USA
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

Member
Joined
Dec 24, 2015
Messages
2,876
This is getting off topic lol.

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.
 
Joined
Aug 16, 2014
Messages
2,987
Location
Webster Groves, MO
WCA
2013BARK01
This is getting off topic lol.



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.
But can't you just consider the effect of the move sequences instead of the infinite set of sequences producing that effect?
 
Top