Palette 21 is a wooden puzzle with 21 square pieces. The pieces lie inside a 5×5 base, and are also held inside a crossshaped frame. The arms of this cross are three pieces wide and 2 pieces long. By moving the frame horizontally or vertically, the pieces are moved about the 5×5 square. In the solved position the frame is at the bottom right, the top arm of the cross has six green pieces, the left arm has six blue pieces, and the centre has the nine red pieces.
This puzzle were invented by Douglas A. Engel, who also invented various other puzzles such as:
If your browser supports JavaScript, then you can play Palette 21 by clicking the link below:
There are 21 pieces, 6 blue, 6 green, an 9 red. One of the red pieces, the one in the centre, never moves but all the others can be mixed up in every way. This gives 20! / (6!6!8!) = 116,396,280 positions of the pieces for any frame position. The frame can be positioned in 3×3 = 9 ways, so there are really 9·20! / (6!6!8!) = 1,047,566,520 positions.
Matt Galla was first to calculate God's algorithm for this puzzle, and I have been able to replicate his results. If a move is defined as sliding the frame exactly one step in any direction, then every position can be solved in at most 50 moves (or 40.060 on average). If a move is a shift of the frame by any distance in any one direction, then it takes at most 38 moves (average 30.654).
Sliding frame exactly one tile is one move  Sliding frame in one direction is one move  






The four antipodes for the single step moves are:
The five antipodes for the single direction moves are:
Sliding the frame left or right by exactly one tile is denoted by L or R
respectively. In the same way moving it up or down is denoted by U or D.
The rows of the 5×5 square are denoted by the letters A to E from top
to bottom, and the columns 1 to 5 from left to right. Any piece location can
then be specified by a letter/number combination.
Phase 1: Solve the top three green pieces.
Phase 2: Put the next three green pieces in column 5.
Note that the remaining green pieces will be placed in column 5, and only put into place
in row 2 at the end of the next phase.
Phase 3: Solve the blue pieces, and put the greens in place.
Note that in this phase we will build up a string of blue pieces that starts at B4. Eventually
we will have the blue pieces at B4, C4, D4, E4, E3, E2, and from there is is easy to solve.