No.283

$N = 1$ のときはそのまま 1 を出力すればいい.

$N = 2$ のときは魔法陣は作れない.

以下, $N \geq 3$ のときを考える.

まずは No.217 と同様の方法で魔法陣を作る.

スライドパズルがこの魔法陣に到達できるかどうかは, 初期配置をベクトルで表したものと魔法陣をベクトルで表したものの置換の偶奇と初期配置と魔法陣の空きマスのマンハッタン距離の偶奇が一致するときである. (参考)

これが成立するときは, 作った魔法陣をそのまま出力する.

成立しないときは魔法陣を以下の通り変形する.

$N$ が偶数のときは, 魔法陣を左右反転させる. この結果, 置換は $N^2/2$ 個の互換を加えることになるので, 置換の偶奇は変わらない. また, 空きマスは奇数個移動するので, マンハッタン距離の偶奇は反転する. よって, 置換の偶奇とマンハッタン距離の偶奇を一致させることができる.

$N$ が奇数のときは, 作った魔法陣が対称魔法陣であれば中心に対して対称な特定の2列を置き換える. この結果, 置換は $N$ 個の互換を加えることになるので, 置換の偶奇は反転する. また, 空きマスは偶数個移動するので, マンハッタン距離の偶奇は変わらない. よって, 置換の偶奇とマンハッタン距離の偶奇を一致させることができる. なお, No.217 でヒンディー法で作成していればそれは対称魔法陣である.

置換の偶奇判定は転倒数の偶奇を見ればいい. 転倒数は Binary Indexed Array を使えば高速に計算できる.