1307:마방진 풀기 3, 4일차

결론적으로 풀었다!
그런데 아직 해야할 문제가 많이 남아있다..

일단 코드가 너무 길고, 성능이 엄청 딸리진 않는데, 개선의 부분이 있을 것 같다.

제대로 만드려면 모든 마방진을 구현할 수 있는 알고리즘이 필요한데 그게 의문이다.

현재로써는 단순히 n을 넣으면 n * n에 해당하는 마방진 단 하나가 나오는데, 4 * 4는 880개의 마방진이 존재하고,

5 * 5 는275,305,224개가 존재한다니 참으로 엄청날 수가 없다.

모든 경우의 수를 제공 할 순 없겠지만, 100개정도는 랜덤으로 제공해야 제대로 된 알고리즘이 될거라고 생각한다.

아니면 차원을 높여서 3d구조의 마방진을 만드는것도 나쁘지 않을 것 같다.

그리고 1일차에 소개한 논문의 strachey 알고리즘이 끝까지 소개되어 있지 않은 상태였다.

제대로 된 방법을 아래 위키주소를 첨부한다.

첫 플레 문제였는데 풀게되어서 너무 좋다. 파이썬으로 제출해서 정답을 맞은 사람으로서는 8~9번째 인거 같다.

https://en.wikipedia.org/wiki/Strachey_method_for_magic_squares

Strachey method for magic squares - Wikipedia

 

def make_odd_magicsquare(n):
    # n^2크기 배열 생성
    arr = [[0 for _ in range(n)] for _ in range(n)]
    # 초기 인덱스 첫번째 행의 가운데 위치 now를 설정
    now = [n // 2, 0]
    # 주어진 규칙으로 숫자를 n^2번 배정한다.
    for i in range(1, n**2 + 1):
        x, y = now
        arr[y][x] = i
        new_x = x + 1 if x + 1 < n else 0
        new_y = y - 1 if y - 1 >= 0 else n - 1
        now = (x, y + 1) if arr[new_y][new_x] else (new_x, new_y)
    return arr


def make_double_even_magicsquare(n):
    def fill_num(x, y, d, direction):
        directions = {"NW": (-1, -1), "SW": (-1, 1), "NE": (1, -1), "SE": (1, 1)}
        now_direction = directions[direction]
        value = arr[y][x]
        i = 0
        while 0 <= x + now_direction[0] * i < N and 0 <= y + now_direction[1] * i < N:
            arr[y + now_direction[1] * i][x + now_direction[0] * i] = value + d * i
            i += 1

    # n^2크기 배열 생성
    arr = [[0 for _ in range(n)] for _ in range(n)]
    # 대각선, 0번 행, -1번행 값 삽입
    for i in range(N):
        arr[0][i] = i + 1
        arr[i][i] = 1 + (N + 1) * i if i != 0 else 1
        arr[-(i + 1)][i] = N**2 - N + 1 - (N - 1) * i
        arr[-1][-(i + 1)] = N**2 - i
    # 4 * 4 array swap
    for i in range(N // 4):
        arr[0][i * 4 + 1], arr[-1][-(i * 4 + 2)] = (
            arr[-1][-(i * 4 + 2)],
            arr[0][i * 4 + 1],
        )
        arr[0][i * 4 + 2], arr[-1][-(i * 4 + 3)] = (
            arr[-1][-(i * 4 + 3)],
            arr[0][i * 4 + 2],
        )
    # diagonal value
    for i in range(2, N, 2):
        if arr[0][i] > N:
            fill_num(i, 0, -(N + 1), "SE")
        else:
            fill_num(i, 0, N + 1, "SE")

        if arr[N - 1][N - (i + 1)] > N:
            fill_num(N - (i + 1), N - 1, -(N + 1), "NW")
        else:
            fill_num(N - (i + 1), N - 1, N + 1, "NW")

        if arr[0][i - 1] > N:
            fill_num(i - 1, 0, -(N - 1), "SW")
        else:
            fill_num(i - 1, 0, N - 1, "SW")

        if arr[N - 1][N - i] > N:
            fill_num(N - i, N - 1, -(N - 1), "NE")
        else:
            fill_num(N - i, N - 1, N - 1, "NE")

    return arr


def iterize(function):
    def wrapper(args):
        if (
            isinstance(args, list)
            or isinstance(args, set)
            or isinstance(args, tuple)
            or isinstance(args, dict)
        ):
            return list(map(wrapper, args))
        else:
            return function(args)

    return wrapper


@iterize
def magic_plus1(x):
    return x + ((N // 2) ** 2) * 1


@iterize
def magic_plus2(x):
    return x + ((N // 2) ** 2) * 2


@iterize
def magic_plus3(x):
    return x + ((N // 2) ** 2) * 3


def strachey_algorithm(n):
    arr = [make_odd_magicsquare(n // 2) for _ in range(4)]
    arr[1] = magic_plus2(arr[1])
    arr[2] = magic_plus3(arr[2])
    arr[3] = magic_plus1(arr[3])
    #swap left k column k = n // 4 arr0, arr2
    for i in range(n // 4):
        for j in range(n // 2):
            arr[0][j][i], arr[2][j][i] = arr[2][j][i], arr[0][j][i]
    #swap right k-1 column
    for i in range(n // 4 - 1):
        for j in range(n // 2):
            arr[1][j][-(i + 1)], arr[3][j][-(i + 1)] =arr[3][j][-(i + 1)], arr[1][j][-(i + 1)]
    #swap arr[0]-left-medium cell <-> arr[2]-medium-medium cell,
    #swap arr[2]-left-medium cell <-> arr[0]-medium-medium cell,
    arr[0][n // 4][n // 4], arr[2][n // 4][n // 4] = arr[2][n // 4][n // 4], arr[0][n // 4][n // 4]
    arr[2][n // 4][0], arr[0][n // 4][0] = arr[0][n // 4][0], arr[2][n // 4][0]
    arr = [
        [i + j for n0, i in enumerate(arr[0]) if n0 == n1]
        for n1, j in enumerate(arr[1])
    ] + [
        [i + j for n0, i in enumerate(arr[2]) if n0 == n1]
        for n1, j in enumerate(arr[3])
    ]
    arr = [arr[i][0] for i in range(n)]
    return arr

if __name__ == "__main__":
    N = int(input())
    if N % 2 == 1:
        for i in make_odd_magicsquare(N):
            print(*i)
    elif N % 4 == 0:
        for i in make_double_even_magicsquare(N):
            print(*i)
    else:
        for i in strachey_algorithm(N):
            print(*i)