# What position takes the most moves to solve for the jail puzzle (Klotski)?

For full details on the puzzle: https://en.wikipedia.org/wiki/Klotski#Khun_Chang_Khun_Phaen

May only use the legal pieces available in the original puzzle. A move is counted as moving any piece on square in any direction.

The minimum number of moves for the original puzzle is 81.
2442
2442
0330
2112
2112

This position for example takes a minimum of 126 moves to solve:
4420
4420
1233
2212
2112

Where 4 is the main piece, 2 is the vertical pieces, 3 is the horizontal pieces, 1 are the single square pieces and 0 are the gaps. The exit is at the base of the puzzle.

What is the positions which takes the most moves to solve?

• This is more a math problem. You can solve this by creating an graph of all positions and the transitions between them. Find the longest path between any node and an end node. Do not visit the same node twice else you can go on forever. – Toon Krijthe Jun 6 '18 at 10:41

As the wikipedia article states, there are many, many names for that puzzle. I'm a bit surprised, the Wikipedia article does not mention an exhaustive analysis documented in the book Winning Ways for your Mathematical Plays, Vol 2. The authors state that the longest possible puzzle has the starting position:

``````1441
2442
2022
1021
5566
``````

and the ending position is the flipped version of that position. They call it the "Century and a half" puzzle, and state it's the longest sliding block puzzle with those pieces. They also provide a "map" that shows the entire space of configurations, and how to move between them.

• Does the book mention how many moves it takes? – silent-tiger Jun 8 '18 at 1:41
• Nope. But, from the name of the puzzle, one can infer it's 150 moves. – John Jun 8 '18 at 1:45