1부터 9까지를 3x3에 한 번씩 넣어 가로 3줄, 세로 3줄, 대각선 2줄의 합이 모두 같게 만드는 문제다.
경우의 수가 9!인 362880개다. 전부 만들어보고 확인해도 된다.
순열 만들기
자리를 맞바꾸는 방식으로 순열을 만든다.
def do(n):
if n == 9:
check(li)
return
for i in range(n, 9):
li[i], li[n] = li[n], li[i]
do(n + 1)
li[i], li[n] = li[n], li[i]
n 번째 자리에 n 이후의 원소를 하나씩 끌어와 놓고, 다음 자리로 내려갔다가, 돌아오면 되돌린다. 리스트 하나를 계속 고쳐 쓰므로 새로 만드는 게 없다.
여덟 줄 검사
리스트 9개를 한 번에 풀어놓고 여덟 줄의 합을 직접 적었다.
def check(li):
a, b, c, d, e, f, g, h, i = li
c1 = a + b + c
c2 = d + e + f
c3 = g + h + i
c4 = a + d + g
c5 = b + e + h
c6 = c + f + i
c7 = a + e + i
c8 = c + e + g
if c1 == c2 == c3 == c4 == c5 == c6 == c7 == c8:
...
3x3이라 줄이 여덟 개뿐이고, 인덱스로 도는 것보다 이렇게 적는 게 틀릴 여지가 적었다. 크기를 키우면 못 쓰는 방식이다.
답을 편차로 출력하기
숫자를 그대로 찍지 않고 5를 기준으로 얼마나 떨어져 있는지로 찍었다.
for i, e in enumerate(li):
if e > 5:
print(f'5+{e-5}', end=' ')
elif e < 5:
print(f'5-{5-e}', end=' ')
else:
print('5±0', end=' ')
이렇게 보면 답 8개가 전부 가운데가 5±0 이고, 마주 보는 칸끼리 부호만 반대인 같은 값이라는 게 눈에 들어온다. 1~9의 평균이 5이고 한 줄의 합이 15로 고정되어 있으니 그럴 수밖에 없는데, 숫자로 볼 때는 안 보이던 게 표기를 바꾸니 보였다.
5x5는 못 했다
같은 방식으로 넓히려다 멈췄다.
n = 5
avg = (n ** 2 + 1) // 2
square = [[avg for j in range(n)] for i in range(n)]
가운데 값이 (n²+1)/2 이라는 것까지 잡아놓고 do 함수 본문에 # Not finished 만 남아 있다.
25!은 전부 만들어볼 수 있는 크기가 아니다. 위에서 본 편차 구조를 조건으로 써서 후보를 줄이는 쪽으로 가야 하는데 거기서 더 나가지 못했다.