３×３の場合
（１）各辺のピースを中央のピースに合わせる　最悪で（３＋２＋１＋０）＝６回
（２）角のピースを合わせる　最悪で（３＋２＋１＋０）＝６回
よって６＋６＝１２回

４×４の場合
（１）各辺のピースに対して対応する中央のピースを見つける
最悪で（４×４−１）＋（４×３＋２×１−１）＋（４×２＋２×２−１）＋（４×１＋２×３−１）＋（２×４−１）＋（２×３−１）＋（２×２−１）＋（２×１−１）＝６４回
（２）角のピースを合わせる　最悪で（３＋２＋１＋０）＝６回
（３）２×２の場合に帰着　最悪で３回
よって６４＋６＋３＝７３回

これが最善手かどうかはわからんが