Я бы на вашем месте обратился к математической моделе «Пятнашек».
Это бы позволило оптимизировать алгоритм.
Например, для перемешивания кусочков не нужно бы было делать цикл из N перемещений собранного пазла (фактически разбирать его). Достаточно бы было пронумеровать кусочки, произвольно разместить их на игровом поле, и воспользовавшись формулой, узнать о существовании решения (если решения не существует, то ЕСЛИ не ошибаюсь — достаточно переставить любые соседние кусочки).
Если анимированно отображать процесс перемешивания — то так даже интереснее. Будет очень быстрое мелькание, которое, тем не менее, за пару секунд перемешает всё до неузнаваемости.
Создаем пазл для iPhone