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.
This position for example takes a minimum of 126 moves to solve:
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?