[4월의 퍼즐] 제곱수 십자수

십자수^Cross-number풀이 퍼즐이란 기존의 십자말풀이 퍼즐을 숫자로 바꾼 것이다. 바꿨다는 말 그대로 칸마다 0부터 9 중 하나를 적어 원래 퍼즐처럼 가로로, 또는 세로로 읽으면 된다. 예컨대 2, 0, 2, 3이 가로(또는 세로)로 나란히 나열되어 있으면 그대로 2023으로 읽으면 되는 것이다.

십자수 퍼즐에 등장하는 어떤 숫자도 0으로 시작해선 안 되며, 특별 지시사항이 없는 이상 한 숫자가 두 번 이상 등장해서는 안 된다. HORIZON 퍼즐 팬이라면 이미 박부성 교수님께서 내신 십자수풀이 퍼즐을 풀어본 경험이 있어 익숙하리라 믿는다.

기존의 십자수풀이 퍼즐에서는 한 자리 수는 등장 숫자로 취급하지 않지만, 이번 퍼즐에서만 큼은 인정하기로 하자. 예를 들어 좌우가 막힌 빈 칸이 있어, 9라고 적혀있으면 숫자 9도 십자수풀이에 등장한 것으로 가정한다. 등장숫자가 많아질수록 중복 가능성이 올라가므로 더 어려운 조건을 추가한 셈이다.

진후는 다음 조건을 만족하는 n×n 십자수풀이 퍼즐이 가능한지 찾고 있다.

1. 등장 숫자는 모두 제곱수이다.

2. 가로로 등장하는 숫자 개수와 세로로 등장하는 숫자 개수 모두 n개이다.

3. 가로로 등장하는 숫자들의 자릿수는 모두 다르고, 세로로 등장하는 숫자들의 자릿수도 모 두 다르다.

가장 간단한 경우인 2×2의 경우 대칭을 제외하면 다음과 같은 경우만 가능하다.

가로로 등장하는 숫자는 16과 4로, 서로 자릿수가 다른 두 제곱수이다. 세로로 등장하는 숫자는 1과 64로 역시 서로 자릿수가 다른 두 제곱수이다. 등장하는 숫자는 가로와 세로를 통틀어 중복되는 것은 없다.

여기서 문제, 3×3의 경우 같은 조건을 만족하는 십자말풀이 퍼즐이 존재할까? 존재하면 예시를 찾고, 없다면 불가능을 증명해보자.