오일러 프로젝트 68

아래와 같이 바방진과 유사한 성질을 가진 도형이 있습니다. 1부터 6까지의 숫자가 한 번씩만 사용되었고, 선을 따라 합을 구하면 항상 9가 됩니다.

바깥으로 뻗친 가지 중에서 가장 숫자가 낮은 것부터 시작해서 직선들을 시계 방향으로 돌아가며 나열하면, 도형의 모양을 숫자로 나타낼 수 있습니다. 위 그림의 예를 들면 4,3,2; 6,2,1; 5,1,3 이 됩니다.

위 도형으로는 네 가지 다른 합계를 가지도록 배열할 수 있는데, 다음과 같은 여덟개의 풀이가 존재합니다.

• 합계 9 : 4,2,3; 5,3,1; 6,1,2
• 합계 9 : 4,3,2; 6,2,1; 5,1,3
• 합계 10 : 2,3,5; 4,5,1; 6,1,3
• 합계 10 : 2,5,3; 6,3,1; 4,1,5
• 합계 11 : 1,4,6; 3,6,2; 5,2,4
• 합계 11 : 1,6,4; 5,4,2; 3,2,6
• 합계 12 : 1,5,6; 2,6,4; 3,4,5
• 합계 12 : 1,6,5; 3,5,4; 2,4,6

하나의 풀이에 대해서 각 숫자를 모두 이어 붙이면 9자리의 숫자를 만들 수 있고, 그 중에서 가장 큰 것은 432621513이 됩니다.
이제 아래와 같은 도형에다 마방진의 성질을 가지도록 1부터 10까지의 숫자를 채우고, 같은 방식으로 풀이 숫자를 이어붙이면 16자리 혹은 17자리의 숫자가 만들어집니다. 이 때, 16자리 숫자 중에서 가장 큰 것은 무엇입니까?

https://euler.synap.co.kr/problem=68

접근

이상하게 포럼에 답변이 많이 안달려 있는 문제이다. 내가 풀었던 시점 (2017년 9월) 기준으로 10개도 안되는 글만 달려 있었다.

설명을 위해서 왼쪽의 그림과 같이, 10개의 칸에 A부터 I까지의 이름을 붙였다. 이 도형의 5개의 변의 숫자의 합을 모두 더한 것을 식으로 표현하면 (A + F + G) + (B + G + H) + (C + H + I ) + (D + I + J) + (E + J + F) 이고, 이를 정리하면 (A + B + C  + D + E) + 2(F + G + H + I + J) 가 된다. 즉 안쪽 오각형의 꼭지점에 해당하는 수들은 두 번씩 더해지는 것이다.

마방진 특성상 모든 변의 수의 합은 같아야 하므로 총합을 5로 나눈 값이 한 변의 합이 되어야 한다. 문제의 조건은 각 변의 숫자들을 순서대로 이어붙이면 16자리 혹은 17자리 숫자가 만들어진다. 그런데 만약 10이 F, G, H, I, J 중에 하나에 위치한다면 전체를 이어붙였을 때 두 번 들어가므로 17자리 숫자가 만들어질 것이다. 따라서 10은 A, B, C, D, E 중 하나에 위치해야 한다.

그리고 이어붙인 수 중에서 최대값을 만들어야 하니, 다른 9, 8, 7, 6 도 바깥에 위치해야 한다. 따라서 오각형의 꼭지점에 해당하는 F, G, H, I, J에 1, 2, 3, 4, 5가 (순서를 달라질 수 있지만) 들어가게 된다. 이렇게 구성하면 한 변의 길이가 14로 계산된다.

끝으로 숫자를 이어붙일 때에는 외곽에 있는 원 중에서 숫자가 가장 작은 것부터 시계방향으로 만들어나간다고 했으니, 6을 A에 고정해두고 생각하면 좀 편할 것이다.

1. 6을 제외한 [10, 9, 8, 7] 의 각 순열과 [1, 2, 3, 4, 5]의 각 순열을 서로 이어붙인다.
2. 매 순열의 조합에 대해서 각 변을 구성하는 인덱스는 (i, i+5, i+6) 가 된다. (i = 0 ~ 4) 단, 마지막에 i + 6 == 10 이면 5로 대체한다.
3. 각 변에 오는 숫자들의 합이 모두 14가 된다면 각 변의 숫자들을 순서대로 이어붙인 후 집합에 추가한다.
4. 집합 중에서 가장 큰 값을 구한다.

def perms(xs):
    def helper(head, tail, n):
        if n == 0:
            yield head
            return
        for i, x in enumerate(tail):
            yield from helper((*head, x), (*tail[:i], *tail[i+1:]), n-1)
    yield from helper((), xs, len(xs))


def main():
    a = 6
    s = set()
    outer, inner = [10, 9, 8, 7], [1,2,3,4,5]
    for xs in perms(outer):
        for ys in perms(inner):
            ks = [a, *xs, *ys]
            edges = [(ks[i], ks[i+5], ks[i + 6 if i != 4 else 5]) for i in range(5)]
            if all(sum(edge) == 14 for edge in edges):
                s.add(''.join(''.join(str(x) for x in edge) for edge in edges))
    print(max(s))


main()