마방진

마방진은 정사각형 격자 안에 숫자를 배열하여 모든 행, 열, 대각선의 합이 동일하게 되도록 하는 숫자 배열입니다. 

$$
\begin{array}{|c|c|c|}
\hline
8 & 1 & 6\\
\hline
3 & 5 & 7\\
\hline
4 & 9 & 2\\
\hline
\end{array}
\\
$$
$$
\text{magic sum : 15}
$$

이러한 배열을 대충 파이썬 코드를 작성해서 찾아보면 $3 \times 3$뿐만 아니라 더 큰 수에서도 찾을 수 있으며 

import numpy as np
from multiprocessing import Pool

# 홀수 차수의 마방진 생성
def generate_odd_magic_square(n):
    magic_square = np.zeros((n,n), dtype=int)
    num = 1
    i, j = 0, n//2
    
    while num <= n*n:
        magic_square[i, j] = num
        num += 1
        newi, newj = (i-1) % n, (j+1) % n
        if magic_square[newi, newj]:
            i += 1
        else:
            i, j = newi, newj
            
    return magic_square

# 4n차수의 마방진 생성
def generate_doubly_even_magic_square(n):
    arr = [[(n*y)+x+1 for x in range(n)]for y in range(n)]
    for i in range(0,n//4):
        for j in range(0,n//4):
            arr[i][j] = (n*n + 1) - arr[i][j];
    for i in range(0,n//4):
        for j in range(3 * (n//4),n):
            arr[i][j] = (n*n + 1) - arr[i][j];
    for i in range(3 * (n//4),n):
        for j in range(0,n//4):
            arr[i][j] = (n*n + 1) - arr[i][j];
    for i in range(3 * (n//4),n):
        for j in range(3 * (n//4),n):
            arr[i][j] = (n*n + 1) - arr[i][j];
    for i in range(n//4,3 * (n//4)):
        for j in range(n//4,3 * (n//4)):
            arr[i][j] = (n*n + 1) - arr[i][j];
    return np.array(arr)

# 4n+2차수의 마방진 생성
def generate_singly_even_magic_square(s):
    if s % 2 == 1:
        s += 1
    while s % 4 == 0:
        s += 2
    q = [[0 for j in range(s)] for i in range(s)]
    z = s // 2
    b = z * z
    c = 2 * b
    d = 3 * b
    o = generate_odd_magic_square(z)
    for j in range(0, z):
        for i in range(0, z):
            a = o[i][j]
            q[i][j] = a
            q[i + z][j + z] = a + b
            q[i + z][j] = a + c
            q[i][j + z] = a + d
    lc = z // 2
    rc = lc
    for j in range(0, z):
        for i in range(0, s):
            if i < lc or i > s - rc or (i == lc and j == lc):
                if not (i == 0 and j == lc):
                    t = q[i][j]
                    q[i][j] = q[i][j + z]
                    q[i][j + z] = t
    return np.array(q)

def generate_magic_square(n):
    if n % 2 == 1:
        return generate_odd_magic_square(n)
    elif n % 4 == 0:
        return generate_doubly_even_magic_square(n)
    else:
        return generate_singly_even_magic_square(n)

def is_valid_magic_square(magic_square):
    n = len(magic_square)
    magic_sum = np.sum(magic_square, axis=0)[0]
    return (
        all(np.sum(magic_square, axis=0) == magic_sum) and
        all(np.sum(magic_square, axis=1) == magic_sum) and
        np.sum(np.diag(magic_square)) == magic_sum and
        np.sum(np.diag(np.fliplr(magic_square))) == magic_sum
    )

def worker(n):
    magic_square = generate_magic_square(n)
    result_str = f'Magic Square of order {n}x{n}:\n'
    result_str += str(magic_square) + '\n'
    result_str += f'Magic sum: {np.sum(magic_square, axis=0)[0]}\n'
    result_str += f'Is valid magic square: {is_valid_magic_square(magic_square)}\n'
    return result_str

if __name__ == "__main__":
    orders = list(range(3, 11))
    with Pool() as pool:
        results = pool.map(worker, orders)
    for result in results:
        print(result)

$$
\begin{array}{|c|c|c|c|}
\hline
16 & 2 & 3 & 13\\
\hline
5 & 11 & 10 & 8\\
\hline
9 & 7 & 6 & 12\\
\hline
4 & 14 & 15 & 1\\
\hline
\end{array}
$$
$$
4 \times 4 \quad \text{magic sum : 34}
$$
---
$$
\begin{array}{|c|c|c|c|c|}
\hline
17 & 24 & 1 & 8 & 15 \\
\hline
23 & 5 & 7 & 14 & 16 \\
\hline
4 & 6 & 13 & 20 & 22 \\
\hline
10 & 12 & 19 & 21 & 3 \\
\hline
11 & 18 & 25 & 2 & 9 \\
\hline
\end{array}
$$
$$
5 \times 5 \quad \text{magic sum : 65}
$$
---
$$
\begin{array}{|c|c|c|c|c|c|c|}
\hline
30 & 39 & 48 & 1 & 10 & 19 & 28 \\
\hline
38 & 47 & 7 & 9 & 18 & 27 & 29 \\
\hline
46 & 6 & 8 & 17 & 26 & 35 & 37 \\
\hline
5 & 14 & 16 & 25 & 34 & 36 & 45 \\
\hline
13 & 15 & 24 & 33 & 42 & 44 & 4 \\
\hline
21 & 23 & 32 & 41 & 43 & 3 & 12 \\
\hline
22 & 31 & 40 & 49 & 2 & 11 & 20 \\
\hline
\end{array}
$$
$$
7 \times 7 \quad \text{magic sum : 175}
$$
---
$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
64 & 63 & 3 & 4 & 5 & 6 & 58 & 57 \\
\hline
56 & 55 & 11 & 12 & 13 & 14 & 50 & 49 \\
\hline
17 & 18 & 46 & 45 & 44 & 43 & 23 & 24 \\
\hline
25 & 26 & 38 & 37 & 36 & 35 & 31 & 32 \\
\hline
33 & 34 & 30 & 29 & 28 & 27 & 39 & 40 \\
\hline
41 & 42 & 22 & 21 & 20 & 19 & 47 & 48 \\
\hline
16 & 15 & 51 & 52 & 53 & 54 & 10 & 9 \\
\hline
8 & 7 & 59 & 60 & 61 & 62 & 2 & 1 \\
\hline
\end{array}
$$
$$
8 \times 8 \quad \text{magic sum : 260}
$$
---
$$
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
47 & 58 & 69 & 80 & 1 & 12 & 23 & 34 & 45 \\
\hline
57 & 68 & 79 & 9 & 11 & 22 & 33 & 44 & 46 \\
\hline
67 & 78 & 8 & 10 & 21 & 32 & 43 & 54 & 56 \\
\hline
77 & 7 & 18 & 20 & 31 & 42 & 53 & 55 & 66 \\
\hline
6 & 17 & 19 & 30 & 41 & 52 & 63 & 65 & 76 \\
\hline
16 & 27 & 29 & 40 & 51 & 62 & 64 & 75 & 5 \\
\hline
26 & 28 & 39 & 50 & 61 & 72 & 74 & 4 & 15 \\
\hline
36 & 38 & 49 & 60 & 71 & 73 & 3 & 14 & 25 \\
\hline
37 & 48 & 59 & 70 & 81 & 2 & 13 & 24 & 35 \\
\hline
\end{array}
$$
$$
9 \times 9 \quad \text{magic sum : 369}
$$
---
$$
\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
92 & 99 & 1 & 83 & 90 & 17 & 24 & 76 & 8 & 15 \\
\hline
98 & 80 & 82 & 89 & 91 & 23 & 5 & 7 & 14 & 16 \\
\hline
4 & 6 & 88 & 20 & 22 & 79 & 81 & 13 & 95 & 97 \\
\hline
10 & 12 & 19 & 21 & 3 & 85 & 87 & 94 & 96 & 78 \\
\hline
11 & 18 & 25 & 2 & 9 & 86 & 93 & 100 & 77 & 84 \\
\hline
67 & 74 & 51 & 58 & 65 & 42 & 49 & 26 & 33 & 40 \\
\hline
73 & 55 & 57 & 64 & 66 & 48 & 30 & 32 & 39 & 41 \\
\hline
54 & 56 & 63 & 70 & 72 & 29 & 31 & 38 & 45 & 47 \\
\hline
60 & 62 & 69 & 71 & 53 & 35 & 37 & 44 & 46 & 28 \\
\hline
36 & 43 & 50 & 27 & 34 & 61 & 68 & 75 & 52 & 59 \\
\hline
\end{array}
$$
$$
10 \times 10 \quad \text{magic sum : 505}
$$

그때 각 선들의 합은 다음 식을 만족합니다.

$$M = \frac{n(n^2 + 1)}{2}$$

특이한 것은 $8 \times 8$ 마방진 중에서 다음과 같은 배열은

$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
16 & 26 & 1 & 23 & 38 & 52 & 43 & 61 \\
\hline
41 & 63 & 40 & 50 & 3 & 21 & 14 & 28 \\
\hline
36 & 54 & 45 & 59 & 10 & 32 & 7 & 17 \\
\hline
5 & 19 & 12 & 30 & 47 & 57 & 34 & 56 \\
\hline
27 & 13 & 22 & 4 & 49 & 39 & 64 & 42 \\
\hline
62 & 44 & 51 & 37 & 24 & 2 & 25 & 15 \\
\hline
55 & 33 & 58 & 48 & 29 & 11 & 20 & 6 \\
\hline
18 & 8 & 31 & 9 & 60 & 46 & 53 & 35 \\
\hline 
\end{array}$$
$$
8 \times 8 \quad \text{magic sum : 260}
$$

각 수를 제곱해도 마방진이 됩니다.

$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
256 & 676 & 1 & 529 & 1444 & 2704 & 1849 & 3721 \\
\hline
1681 & 3969 & 1600 & 2500 & 9 & 441 & 196 & 784 \\
\hline
1296 & 2916 & 2025 & 3481 & 100 & 1024 & 49 & 289 \\
\hline
25 & 361 & 144 & 900 & 2209 & 3249 & 1156 & 3136 \\
\hline
729 & 169 & 484 & 16 & 2401 & 1521 & 4096 & 1764 \\
\hline
3844 & 1936 & 2601 & 1369 & 576 & 4 & 625 & 225 \\
\hline
3025 & 1089 & 3364 & 2304 & 841 & 121 & 400 & 36 \\
\hline
324 & 64 & 961 & 81 & 3600 & 2116 & 2809 & 1225 \\
\hline
\end{array}
$$
$$
8 \times 8 \quad \text{magic sum : 11180}
$$

import numpy as np

def is_valid_magic_square(magic_square):
    n = len(magic_square)
    magic_sum = np.sum(magic_square, axis=0)[0]

    # Check the sum of each row, column, and the two diagonals
    return (
        all(np.sum(magic_square, axis=0) == magic_sum) and
        all(np.sum(magic_square, axis=1) == magic_sum) and
        np.sum(np.diag(magic_square)) == magic_sum and
        np.sum(np.diag(np.fliplr(magic_square))) == magic_sum
    )

# Provided magic square
magic_square = np.array([
    [256, 676, 1, 529, 1444, 2704, 1849, 3721],
    [1681, 3969, 1600, 2500, 9, 441, 196, 784],
    [1296, 2916, 2025, 3481, 100, 1024, 49, 289],
    [25, 361, 144, 900, 2209, 3249, 1156, 3136],
    [729, 169, 484, 16, 2401, 1521, 4096, 1764],
    [3844, 1936, 2601, 1369, 576, 4, 625, 225],
    [3025, 1089, 3364, 2304, 841, 121, 400, 36],
    [324, 64, 961, 81, 3600, 2116, 2809, 1225]
])

print(is_valid_magic_square(magic_square))