# Palette 21

Palette 21 is a wooden puzzle with 21 square pieces. The pieces lie inside a 5×5 base, and are also held inside a cross-shaped 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:

## The number of positions:

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
Depth# positions
01
12
24
38
416
520
640
768
8132
9164
10297
11416
12778
131,068
142,034
152,902
165,548
Depth# positions
177,758
1814,723
1920,490
2038,665
2153,680
22101,340
23140,664
24264,553
25363,856
26679,674
27926,190
281,715,255
292,305,824
304,220,638
315,574,508
3210,037,660
3312,923,632
Depth# positions
3422,744,263
3528,247,070
3648,050,536
3756,443,214
3891,008,329
3997,557,952
40143,360,318
41129,664,672
42159,303,960
43102,195,262
4487,917,360
4528,144,016
4612,390,136
471,011,138
48125,136
49546
504
Total1,047,566,520
Depth# positions
01
14
28
316
432
564
6128
7250
8442
9841
101599
113042
125790
1311065
1421073
1539898
1675232
17141851
18266471
19497446
Depth# positions
20922511
211695721
223086242
235534932
249755387
2516821968
2628242168
2745839411
2871301348
29104976901
30143627046
31177043276
32186192809
33151142652
3479126738
3519733802
361444614
3713736
385
Total1,047,566,520

The four antipodes for the single step moves are:

The five antipodes for the single direction moves are:

## Notation:

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.

## Solution:

Phase 1: Solve the top three green pieces.

1. Move the frame to the bottom-centre position, i.e. centred on location D3.
2. If there is a green piece at one of the positions B2, B3, B4, C5, D5, E5, E4, E3, E2, D2, C2, then do the move sequence URDL (or its inverse RULD), and repeat that move sequence until the green piece lies at B4. Then go to step d.
3. If, on the other hand, there is a green piece at one of the positions C4, D4, C1, D1, E1, then do the move sequence ULDR (or its inverse LURD), and repeat that move sequence until the green piece lies at B4.
4. Move the green piece from B4 to the top row by doing the move sequence ULURDD.
5. Repeat steps b-d two more times, until the top row is green.

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.

1. Make sure the frame is once again at the bottom-centre position, i.e. centred on location D3.
2. If D3 is green, then do the following steps to make it non-green:
1. Use repetitions of ULDR or URDL to bring a green tile to B2.
2. If E5 is green, then repeat RULD LURD as often as needed until E5 is no longer green.
3. Do U RULD D. This replaces one of the greens in row A, and displaces D3 in the process.
3. Repeat the move sequence URDL (or its inverse RULD) as often as necessary to make locations C2 and D2 not green. If you can make C5 green at the same time, then do so.
4. Repeat move sequence ULDR (or its inverse LURD), until B4 is green, and E2 is not green.
5. Do RULD, which will insert the green piece into column 5.
6. Repeat steps d-e until all three remaining green pieces are in column 5.

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.

1. Make sure the frame is once again at the bottom-centre position, i.e. centred on location D3.
2. Repeatedly do ULDR until you have a position with C1 and D1 red. On very rare occasions this is not possible, and then just make sure that D1 is red. You often have a choice of red(s), so to speed things up do this in such that you have as long a string of blue pieces as possible at B4 downwards.
3. Do LURD three times to return the green pieces to the top.
4. If D2-3 and E1-4 are all red, do RULURDLD once or twice until this is no longer the case.
5. Do ULURDLDR (or its inverse LURULDRD) as often as neccesary to make D2 blue and E1 red.
6. Do RULD three times, putting the green pieces of row B into column 5.
7. Do ULDR, which makes the string of blues one longer than it was before.
8. If the six blue pieces are not yet all in one string at B4, C4, D4, E4, E3, E2, then go back to step c.
9. Do LURD six times, so that the blue pieces now fill column A and row B.
10. Do URDL three times, which moves the blue pieces from row B to column 2, and the greens from column 5 to row B.
11. Do R, to put the frame in the correct position.