# Generate an algorithm to get from one state to another.

#### Jeff Dunham

##### Member
What is the best program to use to get a cube from one unsolved state to another? Like an f2l case to complete OLL (just one example), but not necessarily a solved cube.

#### Tavin25

##### Member
Well it's hard to say but I would suggest you go to playstore/appstore and type in cube solver and then you should get some options and try some of those. But in my opinion i would suggest you learn to do it.

#### KAINOS

##### Member
HARCS is primarily a cube solver (which utilizes human method) but it also works decently as a alg generator

#### PingPongCuber

##### Member
Grubik's has an optimal solver, so I guess it could work. Maybe not if you are trying to get to another unsolved state, but a solved cube should have all of the aspects that you are looking to get out of the algorithm, so I think it should work.
https://www.grubiks.com/solvers/rubiks-cube-3x3x3/
(On second thought, I don't know if it is optimal, but it is at least pretty close)
Hope this helps!

#### Bruce MacKenzie

##### Member
What is the best program to use to get a cube from one unsolved state to another? Like an f2l case to complete OLL (just one example), but not necessarily a solved cube.
Doing the math, if you have a cube state A which you want to take to B:

S * A = B

S * A * A'= B * A'

S = B * A'

So you need to solve both the starting state and the goal state. You then apply the generator for the goal state to the inverse of the starting state. An optimal solution of this product will be an optimal turn sequence to take A to B. You could do this with any optimal solver.

For example I just derived a turn sequence which along with its inverse will convert "Anaconda" to "Cube in Cube" and back.

R U' B L F' R' U F L' F' L U2 D B U' Converter

L U B' U' L' R B R' B' F D R D' F' Anaconda
F' R F' U' R F' U' B U' F U B' U' R' U' F R' F Cube in Cube

Last edited:

#### xyzzy

##### Member
Doing the math, if you have a cube state A which you want to take to B:

S * A = B

S * A * A'= B * A'

S = B * A'

So you need to solve both the starting state and the goal state. You then apply the generator for the goal state to the inverse of the starting state. An optimal solution of this product will be an optimal turn sequence to take A to B. You could do this with any optimal solver.

For example I just derived a turn sequence which along with its inverse will convert "Anaconda" to "Cube in Cube" and back.

R U' B L F' R' U F L' F' L U2 D B U' Converter

L U B' U' L' R B R' B' F D R D' F' Anaconda
F' R F' U' R F' U' B U' F U B' U' R' U' F R' F Cube in Cube
You're right, but OP was asking the wrong question in the thread title. It sounds a lot more like Nilsibert's or KAINOS's answers are what they needed.

#### Jeff Dunham

##### Member
Doing the math, if you have a cube state A which you want to take to B:

S * A = B

S * A * A'= B * A'

S = B * A'

So you need to solve both the starting state and the goal state. You then apply the generator for the goal state to the inverse of the starting state. An optimal solution of this product will be an optimal turn sequence to take A to B. You could do this with any optimal solver.

For example I just derived a turn sequence which along with its inverse will convert "Anaconda" to "Cube in Cube" and back.

R U' B L F' R' U F L' F' L U2 D B U' Converter

L U B' U' L' R B R' B' F D R D' F' Anaconda
F' R F' U' R F' U' B U' F U B' U' R' U' F R' F Cube in Cube
Thank you. The mathematical approach is precisely what I wanted.

#### Bruce MacKenzie

##### Member
You're right, but OP was asking the wrong question in the thread title. It sounds a lot more like Nilsibert's or KAINOS's answers are what they needed.
Yes, when you are solving in stages you're dealing in cosets. One needs to take an arbitrary element of coset A to any member of coset B, say. One needs an optimal solver set up for the particular goal coset. Kociemba's Cube Explorer may be set up for problems such as that. I don't know. I've never used it.

#### xyzzy

##### Member
Yes, when you are solving in stages you're dealing in cosets. One needs to take an arbitrary element of coset A to any member of coset B, say. One needs an optimal solver set up for the particular goal coset. Kociemba's Cube Explorer may be set up for problems such as that. I don't know. I've never used it.
Yup, Cube Explorer can handle that pretty much by default. A restriction is that edge orientation must correspond to the first phase of Thistlethwaite's algorithm (or the ZZ speedsolving method, but I guess you'd be more familiar with Thistlethwaite) and the corner orientation must correspond to Kociemba phase 1 / Thistlethwaite phase 2, so it can't handle arbitrary subgroups/cosets. (Which is rarely useful when generating algs for speedsolving, and it's also not of much theoretical interest, so that's not a big deal.)

Then again, with OP's reply above, I am also now confused about what they really (?) want…

#### brododragon

##### Member
S * A = B

S * A * A'= B * A'

S = B * A'
Can someone explain this to me?

#### xyzzy

##### Member
Can someone explain this to me?
When you have two formulas that have equal value (in this case, "S A" and "B" are assumed to be equal, and we want to find S in terms of A and B), you can apply any operation to both sides of the equation and it would still hold. If you've done any algebra in school, this concept should be fairly familiar (e.g. adding 4 to both sides of "x − 4 = 0" to conclude that x = 4).

Going from the first line to the second line, the operation being done is to right-multiply by A' (the inverse of A). This results in the equation S A A' = B A'. (Note that in group theory, you can't just switch the order in which you multiply things. These things aren't numbers. It's like how U R2 and R2 U affect the cube differently.)

Since we have A A' = identity (the "do nothing" state; this is what it means for A' to be the inverse of A), we can left-multiply this by S to get S A A' = S. Now we can combine this with the previous equation to get S = S A A' = B A'. This is an expression of S in terms of A and B, which is exactly what we wanted.

#### brododragon

##### Member
When you have two formulas that have equal value (in this case, "S A" and "B" are assumed to be equal, and we want to find S in terms of A and B), you can apply any operation to both sides of the equation and it would still hold. If you've done any algebra in school, this concept should be fairly familiar (e.g. adding 4 to both sides of "x − 4 = 0" to conclude that x = 4).

Going from the first line to the second line, the operation being done is to right-multiply by A' (the inverse of A). This results in the equation S A A' = B A'. (Note that in group theory, you can't just switch the order in which you multiply things. These things aren't numbers. It's like how U R2 and R2 U affect the cube differently.)

Since we have A A' = identity (the "do nothing" state; this is what it means for A' to be the inverse of A), we can left-multiply this by S to get S A A' = S. Now we can combine this with the previous equation to get S = S A A' = B A'. This is an expression of S in terms of A and B, which is exactly what we wanted.
I understand the idea, but are the values S, A, and B?

#### Christopher Mowla

I understand the idea, but are the values S, A, and B?
We define cube state as how a cube looks (its unique color pattern). You may know it as a scramble.

Of course, you know that the word "scramble" is also a verb$${}^1$$ (not just a noun as I just defined it--because I equated it to "cube state" in the above statement). In cubing, what takes action is a move sequence (algorithm/maneuver, or whatever you want to call it).

Therefore, a cube state and the algorithm $${}^2$$ which generates it can be thought of as being the same.

Going to the equation Bruce wrote,
Doing the math, if you have a cube state A which you want to take to [cube state] B:

S * A = B
Yes, the * is the multiplication symbol, but S and A are algorithms (which can be thought of as cube states). A cube state is a permutation. A permutation in mathematics can be represented by a permutation matrix. Matrix multiplication is NOT commutative.$${}^3$$ In addition, in a matrix product, the order of operations is the opposite of regular multiplication. That is, we multiply from right-to-left. That is, the right-most matrix is considered to be the first "event" in the the product that takes place.

Therefore, when Bruce said "if you have a cube state A", this means that you start with that cube state's generating move sequence:
A

Then you a do something (execute a second move sequence, let's call it S):
S * A

We will call the result cube state B, which we can also think of as a move sequence which generates the cube state generated by applying algorithm A followed by algorithm S.

S * A = B

As you can see, we are forever going back and forth between interchanging the concept of "cube state" with a move sequence which creates/generates that cube state, as we write these equations.

May I also add that, just like in high school math, $$\frac1x\cdot x\;=\;1$$, for $$x\neq0$$, the 1 here is the multiplicative identity for numbers.

There is also an identity matrix for matrix multiplication. That's why Bruce could cancel $$A * {A}^{-1}$$.$${}^4$$ The two algorithms (cube states) did not cancel to "1", but rather the identity matrix. (Which we can think of as a redundant move sequence or no change in state.)

Footnotes:
1. As you know, the verb definition of scramble in cubing is to bring the cube's cube state away from the desired cube state with an algorithm/move sequence/maneuver.
2. We should say "any algorithm", since there are numerous algorithms which can create the same cube state.
3. The order DOES matter with matrix multiplication. You may recall from high school Algebra 2 that you can write a 1x3 matrix to the left of a 3x1 matrix and then multiply them, but the reverse is not true. But more importantly, permutation matrices are all square matrices of equal dimensions, and thus we can change their order and still multiply them, but the result will almost always be different).
4. The prime symbol (') in cubing is equivalent to the $${}^{-1}$$ symbol in mathematics.

Last edited:

#### Bruce MacKenzie

##### Member
I understand the idea, but are the values S, A, and B?
S, A and B in general are elements of a mathematical group. In the present context, they stand for states of the cube. A cube state may be represented by a sequence of turns which give the state when applied to a solved cube. A product A * B is found by applying a turn sequence which gives state B from a solved cube to a solved cube followed by a turn sequence which gives state A when applied to a solved cube.

Representing cube states with turn sequences is rather limited. It is useful to represent cube states as a permutation. The states of the cube then form a permutation group. A straightforward way to do this is as a permutation of the 48 facelets which are rearranged relative to the center facelets by the face turns. One numbers the facelets/facelet positions 1 to 48 and lists which facelet is in each facelet position. There are straightforward algorithms for applying a permutation to another permutation, inverting a permutation and so forth.

The representation I have used in my own apps is based on rotation matrixes. The face turns apply 90˚ rotations about the four fold axes of the cube to the cubies on that face. These rotations may be represented as permutation matrixes of the axes. Recursively forming products of the 90˚ rotations about the x,y and z axes yields 24 matrixes which comprise the Cubic Rotational Symmetry Group. The cube has twelve edge cubies which may be in 12 edge positions in either of two orientations: 12 x 2 = 24. An edge cubie may be moved to each of the 24 possible states by applying one of the 24 cubic rotational transforms. Likewise a corner cubie may be in any of eight positions in three orientations: 8 x 3 = 24. So I represent a cube state as a list of 20 numbers from 0 to 23 telling which rotation transform to apply to move each cubie from its home position to its present position in the cube.

#### Christopher Mowla

I am confused as to why you posted any of what you did in the post above (considering that I posted what I did prior). So, I will say just two things to keep it brief.
1. I think this topic is too simple to mention some of the details you did. Your simple explicit solution is, in MY opinion, all that the OP could hope to see, considering that he didn't ask about how to actually implement a program to do what he was asking for.

2. I believe you would really like threads like Inversion by Conjugation, as solving that type of equation does require mathematical operations (for which there is no simple expression to help bypass it like the one you provided here for this topic) and some (very little, but much more so than this topic--which requires nearly zero..) familiarity with group theory.

Last edited:

#### brododragon

##### Member
When you have two formulas that have equal value (in this case, "S A" and "B" are assumed to be equal, and we want to find S in terms of A and B), you can apply any operation to both sides of the equation and it would still hold. If you've done any algebra in school, this concept should be fairly familiar (e.g. adding 4 to both sides of "x − 4 = 0" to conclude that x = 4).

Going from the first line to the second line, the operation being done is to right-multiply by A' (the inverse of A). This results in the equation S A A' = B A'. (Note that in group theory, you can't just switch the order in which you multiply things. These things aren't numbers. It's like how U R2 and R2 U affect the cube differently.)

Since we have A A' = identity (the "do nothing" state; this is what it means for A' to be the inverse of A), we can left-multiply this by S to get S A A' = S. Now we can combine this with the previous equation to get S = S A A' = B A'. This is an expression of S in terms of A and B, which is exactly what we wanted.
We define cube state as how a cube looks (its unique color pattern). You may know it as a scramble.

Of course, you know that the word "scramble" is also a verb$${}^1$$ (not just a noun as I just defined it--because I equated it to "cube state" in the above statement). In cubing, what takes action is a move sequence (algorithm/maneuver, or whatever you want to call it).

Therefore, a cube state and the algorithm $${}^2$$ which generates it can be thought of as being the same.

Going to the equation Bruce wrote,
Yes, the * is the multiplication symbol, but S and A are algorithms (which can be thought of as cube states). A cube state is a permutation. A permutation in mathematics can be represented by a permutation matrix. Matrix multiplication is NOT commutative.$${}^3$$ In addition, in a matrix product, the order of operations is the opposite of regular multiplication. That is, we multiply from right-to-left. That is, the right-most matrix is considered to be the first "event" in the the product that takes place.

Therefore, when Bruce said "if you have a cube state A", this means that you start with that cube state's generating move sequence:
A

Then you a do something (execute a second move sequence, let's call it S):
S * A

We will call the result cube state B, which we can also think of as a move sequence which generates the cube state generated by applying algorithm A followed by algorithm S.

S * A = B

As you can see, we are forever going back and forth between interchanging the concept of "cube state" with a move sequence which creates/generates that cube state, as we write these equations.

May I also add that, just like in high school math, $$\frac1x\cdot x\;=\;1$$, for $$x\neq0$$, the 1 here is the multiplicative identity for numbers.

There is also an identity matrix for matrix multiplication. That's why Bruce could cancel $$A * {A}^{-1}$$.$${}^4$$ The two algorithms (cube states) did not cancel to "1", but rather the identity matrix. (Which we can think of as a redundant move sequence or no change in state.)

Footnotes:
1. As you know, the verb definition of scramble in cubing is to bring the cube's cube state away from the desired cube state with an algorithm/move sequence/maneuver.
2. We should say "any algorithm", since there are numerous algorithms which can create the same cube state.
3. The order DOES matter with matrix multiplication. You may recall from high school Algebra 2 that you can write a 1x3 matrix to the left of a 3x1 matrix and then multiply them, but the reverse is not true. But more importantly, permutation matrices are all square matrices of equal dimensions, and thus we can change their order and still multiply them, but the result will almost always be different).
4. The prime symbol (') in cubing is equivalent to the $${}^{-1}$$ symbol in mathematics.
So, to sum it up, because of this expression:
S * A = B
Which you can solve for S, giving you this equation:
S = B * A'
If you do the reverse of A's scramble to a solved cubed, followed by B, the moves will equal S, right?

Also, If I am correct, it seem like the resulting algorithm will be a bit long, as most scramble sequences are 20 moves long. I have two questions: Does this find the most effecient way, and, is there any way to find the most efferent scramble sequence?

But more importantly, permutation matrices are all square matrices of equal dimensions, and thus we can change their order and still multiply them, but the result will almost always be different).
So, does this allow you to not care about the orientation of certain pieces? If so, can you expand upon that, if not, do you know a way?

One last thing: Is there a way to just care about certain pieces, and not others (which could be represented as grey)?

#### Bruce MacKenzie

##### Member
Also, If I am correct, it seem like the resulting algorithm will be a bit long, as most scramble sequences are 20 moves long. I have two questions: Does this find the most effecient way, and, is there any way to find the most efferent scramble sequence?
In the context of the original post one is using an optimal solver. Once one has applied the turn sequence B to the inverse of A an optimal solution of the product state will be the shortest sequence to convert A to B.

#### Christopher Mowla

So, to sum it up, because of this expression:

Which you can solve for S, giving you this equation:

If you do the reverse of A's scramble to a solved cubed, followed by B, the moves will equal S, right?
That's correct.

In fact, it's better to write it this way to eliminate any avenue for confusion. (No equation is necessary: the equation was only a tool to arrive at the final product ^^.)

Also, If I am correct, it seem like the resulting algorithm will be a bit long, as most scramble sequences are 20 moves long.
I'm not sure what you mean here. If you have access to a solver which can create sub 21 generating move sequences for cube state A, that same solver should be able to find a sub 21 generating move sequence for ABCDEFG....

Does this find the most effecient way
If you have access to a 3x3x3 solver which can find the shortest algorithm possible (by it also ignoring how the centers facelets are twisted on the supercube), yes.

and, is there any way to find the most efferent scramble sequence?
I think I know what you're getting at here, and yes, you are on to something cool, but no, it's not relevant to this cube theory topic. With this topic, you have a well-defined (and unique -- meaning only one way) to find a "converter" (as Bruce called it) sequence S to take you from cube state A to cube state B. Again, as long as you have access to a computer solver, you will be able to find the shortest possible S, no matter what A' and B are, separately.

Now what I think you're seeing potential for, is to look at what sequences A' (or we can simply say sequence A, since the number of required moves A and A' have are equal) and B have--and what they "look like"--separately.

I wrote my first post in this thread to save you from a headache, but there may not be a way to prevent at least a minor one with what I'm about to say. . . If we have two sequences A and B, if there are pieces which are NOT at the intersection of cube states A and B, then:
• If cube state B is the state which affects pieces in slots that are not in cube state A's "reach", then if cube state B affects two or more corner (or edge--or both separately or both simultaneously) slots that cube state A does not affect, we can conjugate cube state B's (not B prime, B possessive) generating move sequence to shuffle the (corner and/or edge) pieces in slots which are not affected by cube state A. And vice versa--and we can of course do this for both cube state A and cube state B if they both happen to affect two or more pieces that the other does not affect.
• We then can combine these two conjugated sequences A' and B to get a conjugate of S that we can call T (now I'm going back to this topic). We then have to conjugate this combined sequence C T C' to become the "converter" sequence S (that is equal to S) of this topic.

I actually used this type of logic to find a set of over 350,000 2-cycle 4x4x4 parity move sequences. From that huge stockpile of algorithms I was able to find move-optimal (in block quarter turns) sequences to several of the 4x4x4 last layer 2-cycle cases which I didn't already find by hand prior to doing the computer search.

If you didn't quite comprehend the bullets above, check out my video about the above 4x4x4 parity algorithm search, starting at this point and going to, say 16 minutes and 33 seconds (about 4 minutes of video) to see this concept in a more concrete form. Of course, this idea applies more to larger cubes than the 2x2x2 or 3x3x3 (simply because there are more pieces in larger cubes), but it can still happen on either (with rather trivial combinations, to say the least). Specifically, in the video, you can think of sequence A' as being the "3-cycle" and sequence B as being the "4-cycle". Combining both makes the "2-cycle" (which you can think of as S).

So, does this allow you to not care about the orientation of certain pieces? If so, can you expand upon that, if not, do you know a way?
As you may see by this point (having investigated the above), this is irrelevant to optimizing the move sequence S, because that is a clearly defined end-goal sequence to find. You can combine not just two, but an infinite number of algorithms together to create that specific S. What you are hinting at is the characteristics of, say, two sequences A' and B (but we can generalize them to X and Y if we want, because A' and B was just a means to obtain the cube state S from Bruce's equation. The moves you want to choose to create state S is entirely up to you and is independent of how you first happened to determine cube state S).

So, yes. As the simplest example, if the UFR corner in cube state S is just twisted +90 degrees in its own location (but was not moved), and you are only assuming to combine two move sequences X and Y together, then any of the three combinations are allowed (for the twist of the UFR corner).
 Cube State A'​ Cube State B​ -90 -90 0 +90 +90 0
One last thing: Is there a way to just care about certain pieces, and not others (which could be represented as grey)?
If you are talking about sequence S, no. How could this be? Maybe if you were limited to (which you are NOT, since you have access to an optimal solver) to find a sequence T, which, if repeated, say, twice, will give you S. Then if there are pieces in two-cycles in T--whose orientation is maintained--then you could "ignore" those pieces in this situation--where, again, you are assuming to repeat sequence T twice to get your S. (This is because a 2-cycle repeated twice will cancel it out = doesn't matter.) But again, this is redundant, inefficient, and strange. Why not just have the single sequence S, and find the (or the few or few dozen) move-optimal generating move sequences to it?

Again, may I say that some concepts I believe you are getting to with this question actually applies to other topics in cube theory, such as Inversion by Conjugation, and most definitely the theory of finding single commutator solutions for any given one of the 43 quitillion/2 even permutation scrambles/positions/cube states.

--> Example 2x2x2 Solve | Example 3x3x3 Solve | Example 4x4x4 Solve.

(The latter because there are numerous X's and Y's in [X,Y] which can generate some even permutation cube state S (or, in general, "elements in the commutator subgroup") --and I'm obviously not just talking about "move sequences", but the actual mathematical structure of the sequences . . .)

Last edited:

#### xyzzy

##### Member
So, does this allow you to not care about the orientation of certain pieces? If so, can you expand upon that, if not, do you know a way?

One last thing: Is there a way to just care about certain pieces, and not others (which could be represented as grey)?
You need to state what exactly you're trying to accomplish because your questions don't make enough sense by themselves to be answered.

The act of ignoring pieces, or ignoring any sort of information in general, is to group things into equivalence classes: you declare by fiat a new notion of equality (an "equivalence relation") where two things are equal under the new notion if everything about them, other than the information you want to ignore, is equal. (This informal definition has some problems and if you want to iron them out, you need to use the proper definition.) The collection of equivalence classes is then a quotient of the original set; anything you can say about your original set that doesn't involve the information to be ignored, you can say the same of the quotient.

In group theory, the types of equivalences and quotients we most care about are those given by subgroups: when you have a group G and a group H contained in G, we can construct an equivalence relation where you don't care about the information "given by H". For example, if you take G to be the collection of last layer cube states and H to be the collection of last layer cube states with all pieces oriented (i.e. the information this has is the permutation of the last layer pieces), then the quotient G/H is roughly what we think of as being the OLL step of the CFOP method.

--- side note: cosets and coset spaces ---
Formally, "ignoring information given by $$H$$" amounts to multiplying by $$H$$, in the sense of taking an input $$g\in G$$ to $$gH:=\{gh:h\in H\}$$. This is because multiplying further by anything in $$H$$ will not change the result: for any $$h_1\in H$$, we have that $$(gH)h_1=g(Hh_1)=gH$$. (We can't reorder operands in group theory, but we can reorder brackets.)

From another point of view, this is the "minimal modification" we need to do to $$g$$ to make it so that it'll ignore anything from $$H$$. There is one very important subtlety here: we're right-multiplying by $$H$$, leading to the left cosets $$gH$$. We could just as well have used left-multiplication by $$H$$ to get right cosets, which leads to a different result—essentially identical, except that you flip the operations all over.

(Why do we "left-multiply" to get "right cosets" and vice versa? Doesn't that seem like the wrong way? The answer to that is that it seems that way because we were focusing on $$g$$ rather than $$H$$; if we treat $$H$$ as the starting point instead, then a left coset is obtained by left-multiplying $$H$$ by $$g$$ and a right coset is obtained by right-multiplying by $$g$$.)

The left cosets $$gH$$ give a partition of $$G$$ into equivalence classes; the quotient is $$G/H:=\{gH:g\in G\}$$, called the left coset space. (The space of left cosets, as it were.) The right cosets similarly give a partition into equivalence classes, with the quotient being the right coset space $$H\backslash G:=\{Hg:g\in G\}$$.

I personally think it's more natural to use right cosets for twisty puzzles (you can literally read off algs left to right, in the order in which the moves are to be applied) but this is contrary to much of how linear algebra (matrices, vector spaces) and abstract algebra (groups, non-commutative rings, modules) are usually taught, with a focus on left actions/cosets/etc. It seems Bruce's and Christopher's posts have been using the left action convention, for example.

tl;dr: this is shorter than an abstract algebra textbook, don't complain
--- end side note ---

This is the abstract description of what's going on when you want to ignore pieces, or some aspects thereof (e.g. orientation). As for a concrete example of how to do it, as I said right at the start of this post, that depends on what exactly you want to accomplish (which you haven't stated, so we're left guessing wildly).

The term permutation matrix might make one think that it captures only permutation, which is technically true (that's why they're called permutation matrices!), but the permutation of the stickers contains information not just about the permutation of the pieces, but also their orientations as well! If you've tried blindsolving, this should be familiar. For example, with Speffz, the letters B, N and Q all refer to the same corner piece, but different stickers, and you can't just replace one of them for another and still correctly solve the cube. Unless you're using an obsolete method like 3OP, the cycles you trace during memorisation are the cycles of the stickers, not cycles of the pieces, and you don't have to go out of your way to fix orientation afterwards if you did the tracing properly.