\(3 \times 3\) 마방진은 쉽다. 세 행, 세 열, 두 대각선의 합이 모두 같으면 된다:

$$ \begin{matrix} 8 & 1 & 6 \\ 3 & 5 & 7 \\ 4 & 9 & 2 \end{matrix} $$

그렇다면 아홉 칸이 모두 서로 다른 완전제곱수인 \(3 \times 3\) 마방진은? 오일러는 1770년에 \(4 \times 4\) 크기로는 만들어 냈다. 하지만 \(3 \times 3\)은 250년이 지난 지금까지 아무도 만들지 못했고, 불가능하다는 증명도 없다. 마틴 가드너가 1996년에 건 \(100\) 상금은 아직 주인을 찾지 못했으며, 해가 존재한다면 그 수들이 \(10^{16}\)을 넘어야 한다는 것까지만 알려져 있다.

2016년 매트 파커(Matt Parker)는 다음 시도를 공개했다:

$$ \begin{matrix} 29^2 & 1^2 & 47^2 \\ 41^2 & 37^2 & 1^2 \\ 23^2 & 41^2 & 29^2 \end{matrix} $$

행과 열의 합은 전부 \(3051\)이지만, 한 대각선이 \(4107\)이고 세 숫자가 중복이다. 이 장렬한 실패는 파커 정사각형(Parker Square)이라는 밈이 되어 "아쉽게 실패한 모든 시도"의 대명사가 되었다.

아홉 개의 서로 다른 완전제곱수로 이루어진 \(3 \times 3\) 마방진을 출력하라. 채점기는 아홉 수가 모두 완전제곱수인지, 서로 다른지, 여덟 줄의 합이 일치하는지를 정확히 검증한다.

파커 정사각형을 그대로 제출하면 어떻게 되는지 궁금하다면, 한번 해 보라. 채점기가 어느 대각선부터 지적하는지 확인할 수 있다.

아홉 항목은 모두 서로 다른 양의 완전제곱수 (자릿수 \(10^5\) 이하)여야 하며, 세 행·세 열·두 대각선의 합이 모두 같아야 한다.

첫째 줄에 정수 \(0\)이 주어진다. 이 값은 무시해도 좋다 (이 문제에 실질적인 입력은 없다).

마방진을 세 줄에 걸쳐 출력한다. 각 줄에 세 개의 정수(마방진의 항목, 즉 완전제곱수 자체)를 공백으로 구분해 출력한다.

riseoj 작성

출처 Original