まぁクソ単純な配列操作じゃね
要するに4x4の配列に1〜16までの数列割り振って16番を操作キャラとして考えて
16番を上下左右に移動させようとした時、移動先の配列が存在するかを判定
盤からはみ出さないなら移動先の配列に書かれた数字と16番を入れ替えるってのを繰り返すだけじゃね？

最初のシャッフルは16番を乱数移動で1000回くらい移動させれば破綻なく混ざると思う