Yukicoder No.217 魔方陣を作ろう
Wikipediaには奇数$\times$奇数か特殊な$n\times n$の場合しか載ってないじゃんと言ってぐぐって見つけてきたのを書いたが、よく見たらWikipediaのでちゃんと尽くされていた。日本語が読めてなかった。
solution
- $(2n+1)\times (2n+1)$: 斜め上に進んでいくやつ
- $4n\times 4n$: $2\times 2$ごとに区切って反転なやつ
- $(4n+2)\times (4n+2)$: $4$倍に膨らませるやつ (LUX法) / 外枠だけ付けるやつ
それぞれ$O(N^2)$。 詳細はWikipedia見て。
implementation
#!/usr/bin/env python3
def magic_square(n):
assert n >= 3
f = [ [ None for _ in range(n) ] for _ in range(n) ]
if n % 2 == 1: # http://d.hatena.ne.jp/ziom/20090619/p1
y, x = 0, n//2
for i in range(n**2):
f[y%n][x%n] = i+1
if f[(y-1)%n][(x+1)%n] is None:
y, x = y-1, x+1
else:
y, x = y+1, x
elif n % 4 == 0: # http://d.hatena.ne.jp/ziom/20090620/p1
for y in range(n):
for x in range(n):
i = y*n+x+1
if (y+1)&2 == (x+1)&2:
y = n-y-1
x = n-x-1
f[y][x] = i
else: # http://d.hatena.ne.jp/ziom/20090621/p1
# [1,2n-2]
f[ 0][ 0] = 1
f[ 0][n-1] = 2
f[n-1][ 1] = 3
for i in range(4,2*n-1):
if i <= n:
x = i-2
y = [n-1, 0][bool(i&2)]
f[y][x] = i
if i == n:
f[y][x] += 3
else:
y = i-n
x = [n-1, 0][bool(i&2)]
f[y][x] = i
if i < n+4:
f[y][x] -= 1
# [n^2-n+1,n^2]
for i in range(1,n-1):
for j in [ 0, n-1 ]:
if f[ j][ i] is not None:
f[n-j-1][i] = n**2 - f[ j][ i] + 1
if f[ i][ j] is not None:
f[i][n-j-1] = n**2 - f[ i][ j] + 1
f[n-1][n-1] = n**2 - f[ 0][ 0] + 1
f[n-1][ 0] = n**2 - f[ 0][n-1] + 1
# recursion
g = magic_square(n-2)
for y in range(n-2):
for x in range(n-2):
f[y+1][x+1] = g[y][x] + 2*n-2
return f
n = int(input())
for row in magic_square(n):
print(*row)