BOJ 1307 마방진

마방진을 구성하는 법에 대한 연구는 역사가 깊어서 위키피디아 문서에 다양한 방법이 소개되어 있습니다.

여기서는 Bubbler의 풀이를 소개합니다.

$n$이 홀수인 경우

여기서는 Siamese method를 사용했습니다. 이는 다음과 같이 1부터 $n^2$까지의 수를 순서대로 채워 넣는 방법입니다.

• 맨 위쪽 가로줄의 가운데 칸에 1을 씁니다.
• 오른쪽 위로 이동하면서 1 큰 수를 쓰는 것을 반복하는데, 표의 오른쪽이나 위로 나갔다면 같은 줄의 맨 왼쪽이나 맨 아래 줄로 이동합니다.
• 수를 쓰려고 하는 칸에 수가 이미 있으면, 이전 칸에서 대신 아래로 한 칸 이동합니다.

이렇게 하면 마방진이 만들어짐은 각 행과 열에 $(x-1) \bmod n$과 $\left\lfloor \frac{x-1}{n} \right\rfloor$들이 한 줄에 한 번씩 모두 등장하는 점과, 두 대각선이 가운데 수를 기준으로 대칭적인 수로 채워지는 것을 이용하여 보일 수 있습니다.

$n$이 4의 배수인 경우

$n$이 짝수인 경우는 모두 method of superposition, 즉 여러 개의 표를 겹쳐서 마방진의 각 칸의 값을 얻는 방법을 사용했습니다.

$n$이 4의 배수라면 다음과 같은 표를 사용할 수 있습니다. 가로 방향으로 $0, 1, \cdots, n-1$을 정방향 또는 역방향으로 배치하는데 한 번은 앞으로, 한 번은 반대로 배치하는 것을 $\frac{n}{4}$번 반복한 뒤 아래 부분을 거울상으로 채우면 됩니다.

0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0
7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7

이 표의 각 가로줄과 대각선에는 0부터 $n-1$까지가 한 번씩 등장하고, 각 세로줄의 합도 동일함을 알 수 있습니다. 또한, 이 표를 90도 돌린 것을 원래의 표와 겹쳐보면, 같은 수의 순서쌍이 존재하지 않음을 알 수 있습니다.

따라서, 두 개의 표를 겹쳐서 각 칸을 $n$진법의 2자리 수로 해석하여 변환한 뒤에, 모든 수에 1을 더하면 마방진이 완성됩니다. $n = 4$의 경우, Albrecht Dürer의 마방진과 유사한 모양이 만들어집니다.

$n = 2m$이고 $m$이 홀수인 경우

먼저 크기 $m$의 마방진을 하나 만들고 가로, 세로로 두 배로 확장합니다.

8 1 6 8 1 6
3 5 7 3 5 7
2 9 4 2 9 4
8 1 6 8 1 6
3 5 7 3 5 7
2 9 4 2 9 4

여기서 $0 \le r, c < m$에 대해 $(r, c), (r+m, c), (r, c+m), (r+m, c+m)$에 서로 같은 수가 있기 때문에, 이러한 네 자리에 0, 1, 2, 3을 겹치지 않게 할당하면서 가로 합, 세로 합, 대각선 합을 모두 같게 만들 수 있으면 마방진을 만들 수 있습니다. 이러한 네 개의 칸의 집합을 set라고 합시다.

조금 더 단순화하기 위해 0, 1, 2, 3을 00, 01, 10, 11로 바꾸고 0과 1로만 이루어진 표를 두 개 만드는 문제로 바꿉니다.

다양한 시행착오 끝에 얻은 두 개의 표는 다음과 같습니다.

0 1 1 0 0 1
0 1 1 0 1 0
0 1 1 0 0 1
1 0 0 1 1 0
1 0 0 1 0 1
1 0 0 1 1 0

1 0 1 0 0 1
0 0 1 0 1 1
1 0 1 0 0 1
0 1 0 1 1 0
1 1 0 1 0 0
0 1 0 1 1 0

각각의 set에 대해, 서로 같은 값을 갖는 위치가 두 쌍이 만들어지는데, 이러한 쌍이 같은 가로줄에 있는지, 같은 세로줄에 있는지, 또는 같은 대각선에 있는지에 따라 분류할 수 있습니다. 각각 H, V, D라고 합시다. 그러면 위의 두 표가 이루는 각 set의 분류는 다음과 같습니다.

H D H
H H D
H D H

D H H
H D H
D H H

두 표가 모든 set에서 서로 다른 분류를 가지면 00, 01, 10, 11이 하나씩 만들어집니다. 반대로, 서로 같은 분류를 가지면 서로 다른 쌍이 만들어지지 않습니다.

위의 경우, 두 번째 표를 시계 방향으로 90도 돌리면 각 set의 분류가 다음과 같이 바뀌며, 두 표는 위의 조건을 충족합니다.

D V D
V D V
V V V

이제 이를 임의의 홀수 $m$으로 확장해 봅시다.

이들의 세로줄을 잘 보면, 각각 1 1 1 0 0 0, 0 0 0 1 1 1, 0 1 0 1 0 1, 1 0 1 0 1 0의 네 가지 패턴 중 하나로 이루어져 있습니다. 1의 위치에 따라 각각 high, low, odd, even으로 이름을 붙입니다.

그러면 두 표를 다음과 같이 확장하면 D가 각각 맨 오른쪽 2줄과 맨 왼쪽 2줄에 체크무늬로 등장하는 패턴을 만들 수 있습니다.

• [low, high] * (m // 2) + [high, low] * (m // 2) + [odd, even]
• [even] + [low, high] * (m // 2) + [low, odd] + ([high, low] * (m // 2))[:-1]

첫 번째 표의 경우 D가 꼭짓점의 옆 칸에서부터 등장하고, 두 번째 표는 D가 꼭짓점 칸에서부터 등장하므로, 두 번째 표를 돌리면 홀짝성에 의해 각 set의 분류가 첫 번째 표와 겹치지 않게 됩니다.

이제 같은 칸에 온 값들을 잘 합성하면 크기 $n$의 마방진을 얻을 수 있습니다.