在一个分成16格(4*4)的方形棋盘上排列15块号牌，其中会有一个空格。棋盘上的号牌的一次合法移动是指将位于空格上、下、左、右的一块号牌移入空格。对于这些牌给定的一种初始排列(图S)，要求通过一系列的合法移动将初始排列转换成自然排列（自然排列为每一行从左到右，排满该行后从下一行最左开始，排到最后一行后以空格结尾结束。具体为1,2,3,4换行;5,6,7,8换行;9,10,11,12换行;13,14,15,空格。图E）。
1 3 4 15
2 5 12
7 6 11 14
8 9 10 13
图S:初始状态
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
图E:目标状态
要求实现：使用最少的合法移动次数实现初始状态转移到目标状态(自然排序)。
输入:初始状态。
输出：初始状态转移到目标状态的合法移动次数，以及每次移动的方法(或者输出每次移动后4*4方形棋盘的号牌的排列情况)。