Suboptimal solvers for the 4x4 and 5x5 cubes?

I am looking for a suboptimal solution algorithm for the 4x4 and 5x5 cubes.

I am pondering about prepending a third phase to Kociemba's two-phase algorithm for the 3x3 cube. The initial phase performs two-layer twists on a 4x4 cube or a 5x5 cube until the stickers on the edge parts and on the side parts line up to form a 3x3 cube. Then Kociemba's two phase algorithms takes over and solves the 3x3 cube.

Does anyone have experience with such an algorithm? I currently don't know how to create the pruning tables for the initial phase. Also I am not sure, if my approach will work at all.

TIA -Werner

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Probably more than three phases will be needed

The standard 4x4x4 cube has about 7.4e+45 positions, while the standard 5x5x5 cube has 2.8e+74 positions. (I looked these up on "Jaap's Puzzle Page" web site.) These numbers seem to indicate your initial phase will require search spaces of around 2e+26 and 6e+54 positions. As these numbers are much higher than the order of the 3x3x3 cube group, for which Kociemba uses two phases, I believe you will need to prepend more than a single phase for these bigger cubes. I am guessing you might be able to do the 4x4x4 with two added phases, perhaps one for the centers, and one for pairing the edges. (In pairing edges, you probably also want to avoid the parity situations, but I won't get into that detail here.) I am guessing three or four added phases may be required for the 5x5x5.

If you try to use too few phases, the number of moves to do each phase may become too large to get a solution for a given phase in a reasonable time. To get good quality (reasonably close to optimal) solutions in a reasonable time, I believe you want to use as few phases as possible, without any given phase needing excessive execution time. You didn't say what kind of execution time or quality of solution (closeness to optimal) you hoped to achieve. I believe it will take a lot of experimenting to find the right compromise between finding a solution quickly enough and a solution that's as close to optimal as you would like.

Note that on this forum, Jaap Scherphuis has an article "The 4x4x4 centres can be solved in 22 moves" in which he talks about a two-phase solution for the centers (or centres). While Jaap used two phases, I assume the centers can be solved in a single phase with an IDA* type of algorithm, possibly using Jaap's phase 1 table as a pruning table (although I think there may be better choices for a pruning table).

Pairing the edges after solving the centers requires temporarily disturbing the solved centers. This would seem to add some complications to the search algorithm, but I believe that can be handled. There may be other ways to split up the problem of going from scrambled 4x4x4 to scrambled 3x3x3 that may avoid this, and perhaps get better solutions as well.

Kociemba considers sub-optimal solutions for the first of his two phases. Let's say you add two phases for the 4x4x4. If you also consider sub-optimal solutions in those two phases, I believe the run-time could increase dramatically over what it would take if only one optimal solution to each phase is considered. If you want solutions generated quickly, I think the number of solutions considered in the earlier phases may have to be kept fairly small.

I will also note that I am working on a five-stage algorithm of solving the 4x4x4. See my post "God's algorithm calculations for the 4x4x4 'squares set'" on this forum and my follow-up posts to that post. It looks like my five-stage algorithm will guarantee a solution of any 4x4x4 position in no more than about 80 slice turns.