Friday 30 June 2023

The 4 x 3 Sliding Block Puzzle

Today I came across the 4 x 3 sliding block puzzle that is a variant of the more famous Sam Loyd sliding block 15-puzzle that features a 4 x 4 configuration with 15 numbers and one blank space. The 4 x 3 puzzle has 11 numbers and one blank space. See Figure 1.


Figure 1

I came across this puzzle in the context of my diurnal age (27116 days) and OEIS  A090166:


 A090166

Number of configurations of the 4 X 3 variant of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.


It turns out that there are exactly 27116 configurations of this puzzle (with empty square in one of the corners) that require a minimum of 49 moves. Up to the maximum of 53 moves, the initial members of the sequence are:

1, 2, 4, 9, 20, 37, 63, 122, 232, 431, 781, 1392, 2494, 4442, 7854, 13899, 24215, 41802, 71167, 119888, 198363, 323206, 515778, 811000, 1248011, 1885279, 2782396, 4009722, 5621354, 7647872, 10065800, 12760413, 15570786, 18171606, 20299876, 21587248, 21841159, 20906905, 18899357, 16058335, 12772603, 9515217, 6583181, 4242753, 2503873, 1350268, 643245, 270303, 92311, 27116, 5390, 1115, 86, 18 

Figure 2 shows a graph of the above numbers:


Figure 2

For this particular so-called 11 puzzle, there are 18 configurations that require the maximum of 53 moves. These are shown in Figure 3.


Figure 3: source

Figure 4 shows a comparison of the 4 x 3 puzzle with other puzzle sizes.


Figure 4: source

Figure 5 shows a 3 x 3 puzzle for which there a two configurations that require the maximum of 31 moves.

Figure 5

No comments:

Post a Comment