Sliding block puzzles

Klotski is a sliding block puzzle in which the goal is to slide rectangular blocks of different sizes within a framed board, from a given start configuration to a desired target configuration.

The standard puzzle is played on a 5x4 board shown below, with 9 blocks of various sizes and two empty squares. The start configuration is shown on the left. The goal is to find a sequence of sliding moves of the blocks such that the red 2x2 piece can be moved out of the board from the middle of the bottom boundary, for example by reaching the target configuration shown on the right.

Start	Target

The minimum number of moves between this start and target configuration is 116. There is a slight subtlety here, namely how exactly moves are counted. Essentially there are three reasonable definitions of what constitutes a move. A unit move slides a single block by 1 unit. This is the definition we mainly use on this page. A straight move slides a single block by any number of units in the same direction. A finger move slides a single block by any number of units, possibly in different directions (in particular, around corners). This corresponds to a finger grabbing a block and moving it to its destination. Note that the Wikipedia page linked above uses the notion of finger moves. In particular, the minimum number of finger moves for Klotski is 81 (attributed to Mardin Gardner). As mentioned before, on this page we mainly consider unit moves, unless specified otherwise.

One now wonders, is this the hardest possible puzzle on the given board and with the given blocks? It turns out the answer is 'No'. The hardness here is measured as the minimum number of moves between two configurations, maximized over all possible pairs of configurations. There is a harder puzzle which requires at least 190 moves to solve, shown below. In fact, there are two possible target configurations which take 190 moves to reach from the given start configuration.

Start	Target 1	Target 2

We can define a graph that has as vertices all possible configurations, and an edge between any two configurations that differ in 1 move. The aforementioned quantity is the diameter of the graph, i.e., the minimum distance between a pair of vertices, maximized over all possible pairs. In addition to the diameter, we may also investigate the number of connected components of the graph, and the sizes of the components. For the classical Klotski puzzle, these graph parameters have the values indicated below. Note that the diameter depends on the definition of moves used (unit moves in this case), however, the number of components and their sizes are the same if another definition is adopted.

Diameter (=moves): 190
Vertices: 65880
Connected components: 898
Component sizes: 2x25955, 4x248, 4x201, 4x181, 4x118, 4x99, 4x98, 4x92, 4x75, 4x73, 2x55, 2x52, 4x47, 4x45, 8x36, 8x33, 4x32, 8x30, 12x29, 4x28, 4x27, 30x26, 4x25, 42x24, 4x21, 8x20, 4x19, 4x18, 64x16, 8x14, 56x12, 4x11, 28x10, 4x9, 100x8, 112x6, 292x4, 36x2

The next immediate question is: Can we design even harder puzzles by varying the board sizes and/or the puzzle blocks? It turns out that the answer is 'Yes', even on boards that are smaller than 5x4, and even more so on larger boards. In particular, by orienting some of the Klotski puzzle blocks differently on the original 5x4 board, we can build a puzzle that needs at least 359 moves to solve! On the 6x4 board, we can devise an absolute devilish puzzle requiring 927 moves. Below we list the hardest and the second-hardest puzzles for various board sizes, found by computer search using the C++ program linked below. This search maximizes the diameter over all possible distributions of rectangular puzzle blocks that fill all squares of the board except two squares which remain empty. For each diameter, we list all possible pairs of configurations (up to symmetries of the board) for which the diameter is attained. It turns out that typically there is only one extremal pair, unlike in the Klotski example from before. Also, the start and target configurations for the extremal pairs often differ only by reflection or rotation, unlike in the Klotski example.

Open Problem 1: Manufacture one of these hard puzzles as a physical object.

Open problem 2: What about puzzles pieces that are not necessarily rectangles? Do they allow making even harder puzzles?

C++ program

The computational results reported below were obtained using the following C++ program: slide.cpp

This program can be used to analyze a variety of rectangular sliding block puzzles, by selecting the board size and the list of blocks on the board. It allows selecting each of the three aforementioned types of moves (i.e., unit moves, straight moves or finger moves). The program can compute the number of connected components and their sizes, the diameter, and the shortest move sequence between two given configurations. Moreover, the program is able to handle labeled and unlabeled blocks (you can also mix both types). For example, blocks in Klotski are unlabeled, i.e., blocks of the same size are indistinguishable. In contrast, in the famous 15-puzzle, blocks are labeled with the integers 1,...,15. Note that for labeled blocks, the number of configurations quickly becomes very big, unmanageable for the program. For example, for the famous 15-puzzle the number of configurations is 16!=20.922.789.888.000 (the program would not be able to handle this). The program also knows a large collection of predefined puzzles from Hordern's book (see below). Compile the program using

g++ -O3 slide.cpp -o slide

Then you can call

./slide -H

to get a detailed explanation of the options.

3x3 board

/ / / /
/ / /
/ /

Diameter (=moves): 19 (hardest puzzle; 10 extremal pairs)
Vertices: 126
Connected components: 1
Component sizes: 1x126

4x3 board

Diameter (=moves): 94 (hardest puzzle)
Vertices: 1350
Connected components: 5
Component sizes: 1x1138, 4x53

Diameter (=moves): 54 (second-hardest puzzle)
Vertices: 1500
Connected components: 15
Component sizes: 1x1364, 2x24, 4x10, 4x8 , 4x4

5x3 board

Diameter (=moves): 191 (hardest puzzle)
Vertices: 5240
Connected components: 97
Component sizes: 1x4668, 4x24, 4x18, 4x15, 4x8, 4x6, 68x4, 8x2

Diameter (=moves): 122 (second-hardest puzzle)
Vertices: 4788
Connected components: 38
Component sizes: 2x1856, 4x65, 4x64, 4x61, 4x37, 4x12, 4x10, 8x8, 4x4

6x3 board

Diameter (=moves): 269 (hardest puzzle)
Vertices: 84000
Connected components: 542
Component sizes: 2x27806, 4x2970, 4x1139, 4x508, 4x184, 4x110, 4x89, 4x70, 4x69, 4x67, 4x60, 4x53, 8x51, 4x48, 8x47, 8x44, 8x40, 8x37, 4x32, 20x30, 8x28, 4x27, 24x24, 20x22, 20x20, 12x18, 56x16, 4x15, 8x14, 16x12, 12x10, 48x8, 48x6, 28x4, 72x3, 48x2

Diameter (=moves): 236 (second-hardest puzzle)
Vertices: 86436
Connected components: 1118
Component sizes: 2x26160, 2x2358, 2x1098, 2x844, 2x764, 2x544, 4x415, 2x406, 4x340, 4x336, 2x322, 4x296, 4x204, 4x188, 4x184, 4x161, 4x118, 4x108, 2x102, 4x100, 4x98, 4x92, 4x88, 4x71, 4x68, 2x54, 8x52, 4x48, 12x38, 8x36, 4x33, 4x32, 8x30, 4x28, 20x26, 12x25, 28x24, 14x22, 8x20, 4x19, 8x17, 84x16, 4x15, 24x14, 24x12, 4x11, 16x10, 4x9, 148x8, 76x6, 4x5, 240x4, 120x3, 140x2

4x4 board

Diameter (=moves): 123 (hardest puzzle)
Vertices: 3330
Connected components: 105
Component sizes: 1x1706, 4x69, 4x45, 4x29, 8x24, 16,15, 6x14, 24x12, 16x8, 16x6, 6x4

Diameter (=moves): 113 (second-hardest puzzle)
Vertices: 14880
Connected components: 161
Component sizes: 1x13324, 4x72, 4x23, 4x18, 4x16, 4x14, 20x12, 16x10, 30x8, 24x6, 4x5, 44x4, 2x2

5x4 board

Interestingly, these two puzzles can be simulated by the original Klotski puzzle hardware, simply by orienting the blocks differently.

Diameter (=moves): 359 (hardest puzzle)
Vertices: 106800
Connected components: 2609
Component sizes: 1x81462, 2x232, 2x128, 2x104, 4x99, 4x97, 4x89, 4x72, 8x67, 4x59, 4x57, 4x55, 4x53, 4x51, 8x48, 6x47, 4x46, 8x44, 4x41, 4x34, 8x30, 4x29, 8x28, 12x27, 4x25, 24x24, 4x23, 16x21, 52x20, 88x18, 12x17, 160x16, 16x15, 42x14, 144x12, 4x11, 108x10, 8x9, 294x8, 4x7, 272x6, 52x5, 966x4, 116x3, 106x2

This start configuration has been found before by Pierre-François Culand for his puzzle 'Little House', but in combination with another target configuration.

/ / /
/ /

Diameter (=moves): 307 (second-hardest puzzle; 6 extremal pairs)
Vertices: 109260
Connected components: 2653
Component sizes: 1x81340, 4x240, 4x219, 4x113, 4x103, 4x100, 4x56, 4x52, 8x47, 4x46, 8x44, 12x42, 4x39, 4x38, 4x37, 4x34, 8x32, 20x31, 16x29, 32x28, 8x27, 72x24, 4x23, 16x22, 4x21, 76x20, 40x18, 28x16, 32x15, 134x14, 4x13, 204x12, 12x11, 112x10, 32x9, 348x8, 16x7, 252x6, 12x5, 926x4, 80x3, 88x2

These puzzles have been known before as 'New Century'.

6x4 board

Diameter (=moves): 927 (hardest puzzle)
Vertices: 766200
Connected components: 32258
Component sizes: 2x140852, 4x3286, 4x1289, 4x1195, 4x1091, 4x991, 4x743, 4x736, 4x692, 4x648, 4x646, 4x620, 4x562, 4x561, 4x486, 4x426, 4x397, 4x378, 8x337, 4x333, 4x332, 4x322, 4x318, 4x311, 4x310, 4x283, 4x274, 4x267, 4x251, 4x247, 4x245, 4x240, 4x235, 4x231, 4x229, 4x223, 4x221, 4x218, 4x212, 4x209, 4x208, 4x204, 4x203, 8x201, 4x197, 4x196, 4x193, 4x190, 4x189, 4x187, 4x180, 4x178, 4x174, 4x173, 4x172, 4x164, 4x163, 4x162, 8x160, 8x159, 4x158, 4x156, 4x154, 4x153, 12x148, 4x146, 4x144, 4x143, 4x142, 12x141, 4x140, 8x139, 4x138, 8x137, 4x136, 4x135, 4x134, 4x132, 8x131, 8x128, 8x126, 8x125, 4x124, 4x122, 8x120, 12x119, 8x118, 4x117, 16x116, 8x115, 4x114, 12x113, 8x112, 12x111, 12x109, 4x107, 8x106, 20x104, 20x101, 8x99, 20x97, 8x96, 4x95, 8x94, 4x92, 8x91, 24x90, 8x89, 8x88, 16x87, 12x86, 8x85, 12x84, 4x83, 12x82, 24x81, 16x80, 32x79, 24x78, 8x77, 12x76, 16x75, 20x74, 16x73, 8x72, 16x71, 28x70, 12x69, 16x68, 12x67, 16x66, 40x65, 24x64, 28x63, 52x62, 16x61, 24x60, 16x59, 36x58, 24x57, 20x56, 12x55, 64x54, 48x53, 48x52, 40x51, 24x50, 32x49, 40x48, 48x47, 48x46, 44x45, 56x44, 40x43, 72x42, 48x41, 72x40, 88x39, 76x38, 84x37, 68x36, 72x35, 80x34, 56x33, 116x32, 64x31, 220x30, 100x29, 136x28, 96x27, 164x26, 128x25, 352x24, 176x23, 172x22, 272x21, 380x20, 128x19, 416x18, 144x17, 588x16, 452x15, 604x14, 112x13, 1904x12, 368x11, 1612x10, 852x9, 3044x8, 660x7, 3528x6, 732x5, 7312x4, 1796x3, 3060x2, 44x1

Diameter (=moves): 586 (second-hardest puzzle)
Vertices: 537520
Connected components: 21958
Component sizes: 2x75052, 4x21336, 4x4349, 2x4346, 4x2586, 4x1313, 4x715, 4x696, 4x633, 4x592, 4x587, 4x542, 4x470, 4x438, 4x424, 4x415, 4x404, 4x299, 4x296, 4x287, 4x285, 4x284, 4x279, 4x259, 4x229, 4x228, 4x218, 4x215, 4x199, 4x194, 4x186, 4x179, 4x168, 12x166, 8x164, 4x159, 4x147, 4x145, 4x138, 4x137, 8x135, 4x134, 8x133, 4x131, 4x130, 4x129, 8x128, 12x127, 4x124, 8x123, 4x121, 4x120, 12x119, 4x118, 12x115, 8x114, 12x109, 4x108, 8x107, 4x106, 6x104, 4x103, 8x102, 4x100, 8x99, 4x98, 16x97, 4x96, 4x94, 8x93, 4x92, 16x91, 4x89, 4x88, 4x87, 8x86, 4x85, 8x84, 4x83, 4x82, 4x81, 12x80, 12x79, 4x78, 8x77, 4x76, 28x75, 8x73, 12x72, 8x71, 12x69, 28x68, 8x67, 8x66, 8x65, 4x64, 4x63, 4x62, 12x61, 28x60, 24x59, 26x58, 12x57, 16x56, 20x55, 16x54, 8x53, 20x52, 8x51, 16x50, 20x49, 16x48, 8x47, 20x46, 8x45, 24x44, 24x43, 44x42, 20x41, 24x40, 32x39, 44x38, 28x37, 32x36, 40x35, 24x34, 60x32, 36x31, 44x30, 28x29, 36x28, 48x27, 44x26, 24x25, 168x24, 48x23, 132x22, 84x21, 152x20, 104x19, 268x18, 84x17, 492x16, 312x15, 204x14, 32x13, 1056x12, 72x11, 1140x10, 640x9, 1666x8, 340x7, 2980x6, 664x5, 5660x4, 2044x3, 1980x2, 96x1

Hordern's book

The standard reference for sliding block puzzles is Edward Hordern's book [Sliding block puzzles - Recreations in mathematics 4; Oxford University Press, 1986]. The puzzles we found are all considerably harder than the ones listed in his book. For comparison, we list some of the puzzles from Hordern's book and the minimum number of moves required to solve them below. Note that Hordern considers only finger moves and straight moves in his book (and not unit moves).

Some solutions given in Hordern's book are not optimal, those are crossed out below. In some of these puzzles, the goal is to slide the 2x2 block and possibly some other block to a particular location (neglecting the target positions of the other blocks), or to move all blocks to specified target positions. In the first case, we take the minimum distance between the start configuration and all possible target configurations with the specified blocks at the specified positions. The given solutions are optimal for each type of moves, but they do not necessarily correspond to the same move sequences.

Puzzles on 5x4 board	Finger moves	Straight moves	Unit moves

C20	45	47	65
C21	26	27	36

C15	63	70	90
C16	40	45	61
C27(a)	60	67 66	85
C27(b)	70	81 76	99
C27(c)	78	89	111
C27(d) (=Klotski)	81	90	116
C28	61	69	87
C29	54 52	64 60	77
C31	55	64	78
C33	20	24	31
C37	40	44	57

C23	28	34	46

C38	21	23	33
C40	21	21	27
C42(a) (Conway's Century)	100	~~113~~ 112	132
C42(b) (Conway's Century and a half)	150	171	207

C18	33	34	45
C19	59	62	83

C30	67 63	71 66	81
C34	39 38	44 43	56
C35	~~101~~ 74	~~110~~ 86	114
C36	28 27	34 29	36
C39	53 40	57 46	55
C41	98	108	135
C43	55	68 66	79
C44	70	80 78	99
C45	113	127	159

C25	40	51	64
C26	49	64 63	80

C32	25	30	39

C24	32	35	48

C17	47	55	71

Puzzles on 6x4 board	Finger moves	Straight moves	Unit moves
C50	41	44	59
C51	71	75	101
C52	90 72	96 76	96