Feather's algorithm

A two-phase computer algorithm created by Michael Feather. It is primarily used for solving the 3x3x3 cube, both suboptimally and optimally in HTM. Not to be confused with a human 3-Color Cube method.

Phases

1. Solve as a 3-color cube (also known as 3-color cube reduction)
2. Final solve (finish as a 6-color cube)

Variants

1. Phase 2 with unlimited solution length (up to and including 16 moves)
2. Phase 2 with solution length limited to 8 moves
3. Phase 2 with solution length limited to 4 moves in the 2x2x2 solver (solution de facto goes: Scrambled → HTR → Solved)

The default 3x3x3 solver setting, which is the 8 move limit for phase 2, was chosen as the best tradeoff between solver's initialization time on one side and generated solution length on the other side. It has the incidental side-effect of providing HTR solutions.

Aside from the two-phase 2x2x2 and 3x3x3 6-color cube solvers, other solvers such as standalone 2x2x2 and 3x3x3 phase 1 solvers or a standalone 3x3x3 phase 2 solver are also available (details).

Features

Feather's algorithm is:

• Employed by a fast optimal Rubik's Cube solver written in JavaScript (details)
• Finding suboptimal solutions while searching for an optimal solution (details)
• Generating both suboptimal and optimal solutions using a single two-phase algorithm (details)
• Often searching at depth N-1 to prove that solution length N is optimal (details)
• Implementing IDA* with unique distance arrays (also known as pruning tables) (details)
• Directly utilizing all 48 cube symmetries (details)
• Producing HTR solutions if solution length for phase 2 is limited (details)
• Not based on the mathematical field of group theory (details)

Stats

3x3x3 phase 1:

• there are 10,863,756,288,000 states:
  • best case: 0 moves
  • worst case: 15 moves
  • average move count: 12.52

3x3x3 phase 2 with unlimited solution length:

• there are 3,981,312 states (663,552 HTR states and 3,317,760 fake HTR states):
  • 663,552 HTR states:
    • best case: 0 moves
    • worst case: 13 moves
    • average move count: 9.54
    • comparison with phase 4 of Thistlethwaite's algorithm: best case: 0 moves, worst case: 15 moves, average move count: 10.13
  • 1,990,656 fake HTR states characterized by a 2-swap of corners and 2-swap of edges (like this):
    • best case: 10 moves
    • worst case: 16 moves
    • average move count: 13.31
  • 1,327,104 fake HTR states characterized by a 3-cycle of corners (like this):
    • best case: 9 moves
    • worst case: 16 moves
    • average move count: 12.66
  • average move count: 12.46

3x3x3 phase 2 with solution length limited to 8 moves:

• there are 117,265 HTR states:
  • best case: 0 moves
  • worst case: 8 moves
  • comparison with phase 4 of Thistlethwaite's algorithm: best case: 0 moves, worst case: 15 moves

2x2x2 phase 1:

• there are 25,515 states:
  • best case: 0 moves
  • worst case: 9 moves
  • average move count: 6.40

2x2x2 phase 2 with solution length limited to 4 moves:

• is reached in at most 10 moves
• there are 24 HTR states:
  • best case: 0 moves
  • worst case: 4 moves (3 moves if excluding scrambles that are optimal half-turn 4-movers)

See also

• Half Turn Reduction
• Thistlethwaite's algorithm
• Korf's algorithm
• Kociemba's Algorithm

External links

• Wikipedia: Feather's algorithm
• Michael Feather's home page with Cube Solvers