4x4 스도쿠는 단 12개뿐이다 — 최소 부분집합을 찾는 멋진 트릭과 함께

본문

문득 떠오른 질문에서 출발한 글입니다. 4x4 스도쿠는 각 행·열·2x2 박스에 1부터 4까지의 숫자가 한 번씩만 나오도록 채우는 퍼즐인데, 저자는 '과연 몇 개의 서로 다른 해가 존재하는가'를 직접 계산해 봅니다.

브루트포스로 해 세기 — 288개

빈 격자에서 시작해 각 셀에 들어갈 수 있는 값을 깊이 우선 탐색(DFS)으로 따라가는 단순한 Python 코드를 작성합니다. 같은 행·열·박스의 셀 목록을 미리 계산해 두고 재귀적으로 채워 나가면 약 0.5초 만에 288개의 해가 나옵니다. 9x9 스도쿠의 해가 약 6.67해(6,670,903,752,021,072,936,960) 개인 것과 비교하면 아주 작은 수입니다. 참고로 행 제약만 고려한 조잡한 상한 (N!)^{N}을 적용하면 4x4에서는 331,776으로 실제보다 크게 부풀려지는데, 이는 열·박스 제약이 실제로 얼마나 많은 경우를 걸러내는지를 보여 줍니다.

'구조적으로 다른' 해 세기 — 12개

스도쿠에서 숫자는 의미 없는 기호일 뿐이라서, 1~4를 임의로 치환(퍼뮤테이션)해도 같은 퍼즐입니다. 치환은 4! = 24가지이므로 구조적으로 다른 해는 이론적으로 288 / 24 = 12개입니다. 저자는 이를 코드로도 검증합니다. 첫 행을 1 2 3 4로 고정하면 모든 구조가 정확히 한 번씩만 표현된다는 사실을 이용하는데, 첫 행이 1 2 3 4로 같은 두 해는 어떤 숫자 치환으로도 서로 변환할 수 없으므로 구조적으로 다르다는 것이 증명됩니다. 초기 격자의 첫 행을 1 2 3 4로 채운 채 탐색을 돌리면 정확히 12개가 나오고, 글에는 그 12개의 해가 전부 도식으로 나열됩니다.

최소 퍼즐 세기 — 85,632개

다음으로 '유일한 해를 갖는 부분 채움(퍼즐)'을 셉니다. 단, 어떤 숫자를 하나라도 빼도 여전히 유일해가 되는 비최소 퍼즐은 제외하고 '최소(minimal) 퍼즐'만 셉니다. 각 해에 대해 모든 셀 부분집합(2^16개 마스크)을 순회하면서, 그 힌트들을 만족하는 해가 자기 자신뿐인지 교집합으로 확인하고, 이미 발견된 퍼즐의 상위집합이면 버리는 방식입니다. 2~3분의 계산 끝에 최소 퍼즐은 총 85,632개, 숫자 치환 기준으로는 3,568개가 나옵니다.

비트마스크 트릭

이 글의 진짜 재미는 부분집합 검사를 비트 연산으로 처리한 점입니다. 부분집합을 비트마스크로 표현하면 mask(Q)가 mask(P)의 부분집합인지는 bitmask(P) & bitmask(Q) == bitmask(Q)로 O(1)에 확인할 수 있습니다. 더 중요한 것은 마스크를 1부터 2^16까지 정수 오름차순으로 순회하면 어떤 집합의 모든 진부분집합이 항상 먼저 방문된다는 점입니다. 따라서 '모든 가능한 부분집합'이 아니라 '지금까지 본 퍼즐'과만 비교해도 최소성 판정이 정확합니다. 최대 부분집합을 찾을 때는 순회 방향을 뒤집으면 됩니다.

n=3(9x9)은 불가능

같은 코드를 9x9에 돌리면 부분집합 수가 2^81에 달해, 4x4에서 약 200초 걸린 것을 근거로 추정하면 우주 나이의 수백만 배 이상이 필요합니다. 실제로 9x9 최소 퍼즐의 총수는 아직 알려지지 않았고 상·하한만 존재합니다. 글 말미에는 '해당되는 최소 퍼즐 수가 해마다 304개와 284개로 갈리는 이유', '12 = 3x2x2 구조를 세 셀로 우아하게 분해하는 증명' 같은 미해결 질문도 소개됩니다. 저자는 4cm 크기로 인쇄하면 치환 기준 102페이지, 하루 한 페이지씩 풀면 102일 만에 모든 4x4 스도쿠를 '완주'할 수 있다는 농담으로 마무리합니다.

Lobsters 반응

• @justinpombrio — 12개의 해를 손으로 찾는 우아한 방법을 제시합니다. 숫자 치환 대칭으로 왼쪽 위 2x2 박스를 1 2 3 4로 고정한 뒤, 3·4행 교환이나 3·4열 교환이라는 두 번째 대칭을 적용해 오른쪽 아래 박스의 '1'을 (3,3) 위치로 옮기면 진짜로 다른 해 3가지를 쉽게 열거할 수 있다고 설명합니다.

원문: baldino.dev / 번역·요약: Trawling