Compound Pruning

[unsolved]

I now have the following databases for the 5x5x5 cube:

1. Distance for corners to be solved with respect to centers for any arrangement (11 moves max).
2. Distance for all edges (middles, wings) to be solved, completing a cage, up to 12 moves from the solved state, given corners are already solved.
3. Distance for all centers to be solved from a solved cage, up to 11 moves.

My question is, can I combine the distances of (1) and (2) for pruning purposes, given an attempt to solve a random scramble?

Example:
I have a scramble where the corners database tells me it takes 9 moves to solve the corners. The edges database indicates, once corners are solved, 11 moves are required to complete the cage.

Does this mean I can prune away the first 19 moves of the search? I know it will take 9 + 11 = 20 moves just to complete a cage, so I can't think of any case where the entire cube can be solved within the same number of moves.

And, in general, can these two pruning distances be combined for an effective compound pruning distance of up to 23 moves?

 

[Lucas Garron]

Does this mean I can prune away the first 19 moves of the search?

No. Unless you prove something special about your pruning tables in particular, the best you can assume is 11.

But I may be misunderstanding what "the edges database indicates, once corners are solved" means. Shouldn't your prune table tell you how long it takes to solve edges, *ignoring corners*?

 

[unsolved]

No. Unless you prove something special about your pruning tables in particular, the best you can assume is 11.

But I may be misunderstanding what "the edges database indicates, once corners are solved" means. Shouldn't your prune table tell you how long it takes to solve edges, *ignoring corners*?

The short answer is: It does ignore corners, and centers. Also, the algs will disturb neither, at least from a non-supercube perspective as far as centers are concerned. The algs won't effect a cube with centers already solved. There is a chance the centers are shuffled or cycled on the same face where they resided originally. I don't have a supercube version of my 5x5x5 solver, so I can't test for that condition.

Here's an example from a 5x5x5 post on the forum where I reversed the scramble:

B' L B' D2 F' D R' U F

This example turned up a 9-move solution in the corners database, and had no corresponding entry in the edges database. That means, definitively, the edges can't be solved in 12 moves. That means the entire cube needs 13 moves or more to solve.

But can it be said that this cube needs at least 22 moves to be solved?

Put another way, does there exist a scrambled cube than can be solved in 21 moves or less with a corner solve distance of exactly 9 and edges that would require 13 or more moves to solve, with no constraint on the disposition of the centers?

It could be possible that the 13 moves to solve the edges also cures the corners, but that means the centers have to be solved in 8 moves or less. And even with 1 center unsolved on two adjacent faces, exactly 8 moves are needed. This would have to be a very special case.

 

[Lucas Garron]

But can it be said that this cube needs at least 22 moves to be solved?

No. Not in the way you want to say it.

Consider the scramble r.
It takes at least 1 move to solve the edges (ignoring corners and centers), and it takes at least 1 move to solve the corners (ignoring edges and centers). But you cannot add 1+1 to get a lower bound for the whole puzzle. The best lower bound is max(1, 1) = 1.

The same holds for 13+9. The best lower bound you can get (in general) is max(9, 13) = 13.

 

[unsolved]

No. Not in the way you want to say it.

Consider the scramble r.
It takes at least 1 move to solve the edges (ignoring corners and centers), and it takes at least 1 move to solve the corners (ignoring edges and centers). But you cannot add 1+1 to get a lower bound for the whole puzzle. The best lower bound is max(1, 1) = 1.

The same holds for 13+9. The best lower bound you can get (in general) is max(9, 13) = 13.

But in the move metric I use, it takes 2 moves to solve your "r" move: R' and 2R' in SiGN.

But your example illustrates the point well enough. I understand now. Thanks.

 

[Lucas Garron]

But in the move metric I use, it takes 2 moves to solve your "r" move: R' and 2R' in SiGN.

In that case, max(2, 1) = 2.
;-)

 

[unsolved]

Well it would still be (1,1) since it's one turn for the corner and one move for the edge. But your example got me thinking that one face turn can also increase an "edge distant count" along with the effected corner count, so 1 move disrupts both piece types. That means, there must exist positions where one turn closer to the solve decrements the distance of the corner-distance-count and the edge-distance-count simultaneously. Face turns can do that, while slice turns only effect edges.

Now if I capture face turns and slice turns as separate counts in each fastest solution to restore a position, then we can say:

max = corner distance + edge distance - face turn count in edge solution

...which should give us the count in the "best case" where each face turn also brings a reduced edge count (which won't always be the case, but we can never know for sure 100% of the time).