# I have a software idea



## brododragon (Jan 9, 2020)

I don't think this has been thought up before, please tell me if I'm wrong.

So, recently, I've been trying to invent a new method, and have been playing around with algorithms, trying to find something that works. After thinking about it fit a bit, I think I found a way to generate algorithms to go from one unsolved state to another.

For simplicities' sake, I'm going to act like this is software. Also, let State 1 be the starting state and State 2 be the ending state.


Spoiler: Probably a really bad idea



Here's the idea: You specify what pieces are where, in a specific orientation for the State 1 (leaving some pieces unspecified). Then, this would be repeated with State 2. Then, the software would generate every possible state of the cube that could be in and still be state 2.

Then the software would find optimal algorithms to go from all possible State 1's to all State 2's, keeping track of the algorithms, their lengths, and where the piece/pieces that need to be moved are. Finally, the shortest algorithm would be selected. If you did not like it, you could look through the algorithms to find one you like.





Spoiler: Probably a better idea



I don’t know how software works, but could you just give “grey pieces” the same value/ID as other “grey pieces” that are the same type (corner/edge/middle).


----------



## ichcubegerne (Jan 9, 2020)

Going from one unsolved state to another is also possible by telling a solver that this is a solved state and to solve it (You can also do this by permuting both states)


----------



## brododragon (Jan 9, 2020)

ichcubegerne said:


> Going from one unsolved state to another is also possible by telling a solver that this is a solved state and to solve it (You can also do this by permuting both states)


I don’t understand.


----------



## ichcubegerne (Jan 9, 2020)

Nevermind, I misunderstood something. But honestly, your idea is pretty trivial^^


----------



## brododragon (Jan 9, 2020)

ichcubegerne said:


> Nevermind, I misunderstood something. But honestly, your idea is pretty trivial^^


Both?


----------



## Bruce MacKenzie (Jan 13, 2020)

brododragon said:


> I don't think this has been thought up before, please tell me if I'm wrong.
> 
> So, recently, I've been trying to invent a new method, and have been playing around with algorithms, trying to find something that works. After thinking about it fit a bit, I think I found a way to generate algorithms to go from one unsolved state to another.
> 
> ...


Your idea has a great deal of merit. It's basically how I approach such problems. Consider the second step of the Petrus algorithm. One has a cube state with a 2x2x2 corner solved which is to be extended to a 2x2x3 block. Assuming the solved block is the DBL corner one restricts the moves to turns of the RUF faces ( which don't mess up the solved block). One then has to move the DFL corner cubie and the BL and the DF corner cubies into their solved positions.

There are 7 corner positions (the DBL position is occupied) and 3 orientations available for the DFL cubie:

Corner States = 7 x 3 = 21

For the the BL cubie there are 9 unoccupied positions and two orientations. For the DF cubie, after the BL cubie is in place there are 8 unoccupied positions and two orientation:

Edge States = (9 x 2) x (8 x 2) = 288

Now one needs an indexing scheme where one maps the 21 corner states to the integers 0 to 20 and the 288 edge positions to the integers 0 to 287. How one does this depends on one's functional representation of the cube. By functional I mean a representation that one can apply face turns to and get a representation of the product. Usually I use a mixed radix compression scheme. Anyway, one needs to take a cube representation and encode it as an index and take an index and decode it to a valid functional representation.

With these tools one can construct move tables. Each index is decoded, the face turns are applied and the product is encoded. In this way a look up table is created where one may look up the index of the result of applying a turn to another index. In the present case one gets a 21x9 corner move table and a 288x9 edge move table.

One now constructs a 21x288 depth table listing the turn depth of all 6,048 states of the (DFL, BL, DB) cubies. Start with the identity cube and mark it as at depth 0. One then applies the generator moves and any product different from identity is marked depth 1. One then applies the generator moves to the depth 1 nodes and marks any new states as depth 2 and so forth until a depth is reached which produces no new nodes.

At this point all the information needed to solve any problem state is at hand. The problem state is indexed and its depth is read in the depth table. With the move tables one applies the generator moves to the parent indexes until a product is found one depth closer to solved. Continue until until the trace reaches the solved state.

In addition the depth table may be used as a pruning table in an IDA algorithm search for more advanced positions, eg taking a 2x2x2 block directly to a 2x3x3 block.

In an IDA (Iterative Deepening Algorithm) solver one applies each of the generator moves to the problem state and tests whether any give the goal state. If not all combinations of two moves are tried. Then all combinations of 3 moves, 4 moves … until a solution is found. To reduce the number of move sequences one has to test one can employ a "pruning table". In the present example the pruning table would be the depth table for the (DFL, BL, DB) cubies. At each node in the search one looks up the depth of the (DFL, BL, DB) cubie arrangement. If this is greater than the number of turns remaining to the target depth one can forget about this node. No solution of the current target length will be found by adding turns to this node. In this way one "prunes" branches from the search tree.


----------



## Ben Whitmore (Jan 13, 2020)

brododragon said:


> So, recently, I've been trying to invent a new method, and have been playing around with algorithms, trying to find something that works. After thinking about it fit a bit, I think I found a way to generate algorithms to go from one unsolved state to another.



Finding an algorithm to get from state A to state B is equivalent to solving the equation AS = B in the algorithm group, which has the solution S = A^-1 B. So finding an algorithm to get from state A to state B is equivalent to finding an algorithm which does the same as A' B, which is equivalent to solving (A' B)' = B' A. If S is this algorithm then applying it to A will result in A A' B = B.

State A: U D' F' R' F' D2 R2 U' R' L2 B D2 F R2 F2 D2 L2 B2 U2 R2
State B: R U' R B R B' R B L U2 B2 D2 L2 B2 R L2 D2 F2 U2

The shortest algorithm from A to B is an optimal solution of

B' A = (R U' R B R B' R B L U2 B2 D2 L2 B2 R L2 D2 F2 U2)' (U D' F' R' F' D2 R2 U' R' L2 B D2 F R2 F2 D2 L2 B2 U2 R2)
= U2 F2 D2 L2 R' B2 L2 D2 B2 U2 L' B' R' B R' B' R' U R' U D' F' R' F' D2 R2 U' R' L2 B D2 F R2 F2 D2 L2 B2 U2 R2

which is B2 U F L R D' U B D' U2 B2 L2 D2 F' L F' D U


----------



## brododragon (Jan 13, 2020)

Ben Whitmore said:


> Finding an algorithm to get from state A to state B is equivalent to solving the equation AS = B in the algorithm group, which has the solution S = A^-1 B. So finding an algorithm to get from state A to state B is equivalent to finding an algorithm which does the same as A' B, which is equivalent to solving (A' B)' = B' A. If S is this algorithm then applying it to A will result in A A' B = B.
> 
> State A: U D' F' R' F' D2 R2 U' R' L2 B D2 F R2 F2 D2 L2 B2 U2 R2
> State B: R U' R B R B' R B L U2 B2 D2 L2 B2 R L2 D2 F2 U2
> ...


Is there any mathematical way to optimize an algorithm? Also, is there a way to exclude certain moves (or include certain moves) in an algorithm?


----------



## Ben Whitmore (Jan 14, 2020)

brododragon said:


> Is there any mathematical way to optimize an algorithm? Also, is there a way to exclude certain moves (or include certain moves) in an algorithm?



What does "optimize" mean? Find the shortest one? The only way we know how to find optimal solutions is basically a brute force search. You can make it faster e.g. with pruning tables, but it still takes a while.

If you want optimal solutions that exclude certain moves, you just have to do the brute force search but only using whatever moves you want. You can use a program like ksolve++ to make a solver that does that.


----------



## brododragon (Jan 17, 2020)

Ben Whitmore said:


> pruning tables


What are those?


----------



## Bruce MacKenzie (Jan 17, 2020)

brododragon said:


> What are those?





Bruce MacKenzie said:


> In addition the depth table may be used as a pruning table in an IDA algorithm search for more advanced positions, eg taking a 2x2x2 block directly to a 2x3x3 block.


See my addendum to my previous reply.


----------

