불가능의 가능성

al고리즘과 자료구조를 배우던 중, 교수님께서는 스도쿠 문제(Sudoku Problem)라는 것을 접하게 되었습니다. 전제는 간단했습니다. 어떤 스도쿠 퍼즐이든 풀 수 있는 알고리즘을 작성하는 것이었습니다. 고전적인 무차별 대입(brute-force) 접근 방식은 단순히 모든 빈 공간을 찾아내고 가능한 모든 후보를 열거합니다. n×n 스도쿠 퍼즐의 경우, 이는 최악의 경우 시간 복잡도를 O(nm)으로 만드는데, 여기서 n은 가능한 숫자의 개수이고 m은 빈 사각형의 수를 나타냅니다. 교수님께서는 저희에게 이보다 나은 최악의 경우 시간 복잡도를 가진 알고리즘을 생각해보라고 도전하셨습니다.

교수님께서 무심코 언급하지 않으신 것은, 이 문제에 대한 효율적이고 지수 함수가 아닌 해결책을 찾는 것이 유명하게 미해결된 수학적 난제라는 점입니다.

다음 강의에서, 현재 컴퓨터 과학에는 이 최악의 시나리오를 능가하는 알려진 해결책이 없다는 것이 밝혀졌습니다. 하지만 저는 이미 이를 해결할 방법을 구상하기 시작했기 때문에, 놓아주기가 너무 아까웠습니다.

저는 스도쿠 퍼즐을 푸는 저만의 전략과 표준 알고리즘 솔버가 작동하는 방식 사이의 차이를 분석하기 시작했습니다. 순진한(naive) 알고리즘은 올바른 보드 상태에 도달할 때까지 맹목적으로 출력을

이론적으로 브루트 포스 (brute-force) 접근 방식을 능가할 수 있는지 확인하기 위해, 문제를 4×4 그리드로 축소했습니다. 각 칸에 _a_부터 _p_까지의 변수를 할당했습니다:

[

사람이 칸 _a_를 볼 때, 무작위 숫자를 테스트하지 않습니다. 그들은 즉시 세 가지 물리적 제약 조건, 즉 해당 칸의 행 (row), 열 (column), 그리고 국소적인 2×2 서브 그리드 (sub-grid)를 교차 참조합니다.

수학적으로 이는 칸 _a_가 고립되어 떠 있는 것이 아니라, 세 개의 서로 다른 집합 (set)이 교차하는 지점에 엄격하게 존재함을 의미합니다:

4×4 보드의 모든 칸을 그에 상응하는 행, 열, 서브 그리드로 매핑함으로써, 저는 12개의 근본적인 제약 집합 (constraint sets)을 생성했습니다.

[

용의자 제거하기

이제 이것은 지수적 탐색 (exponential search)을 즉각적인 논리적 연역 (logical deduction)으로 전환합니다. 만약 칸 _a_가 비어 있다면, 우리는 추측하지 않습니다. 단순히 세 개의 교차하는 집합 안에 있는 알려진 값들을 살펴볼 뿐입니다:

이 집합들의 합집합 (union)을 구하면, 값 _{1, 3, 4}_가 이미 점유되었음을 알 수 있습니다. 순수한 집합 제거 (set elimination)를 통해, _a_는 반드시 _2_여야 합니다. 추측도, 분기 (branching)도, 낭비되는 CPU 사이클도 없습니다.

이와 동일한 제거 논리를 칸 _d_에 적용하면, 집합 1, 5, 7을 교차 참조하여 즉시 _d = 3_임을 밝혀냅니다.
보드의 모든 빈 칸이 이와 같이 강제된 선택지를 갖는다면, 알고리즘은 선형 시간인 O(3m) 내에 결승선까지 곧장 걸어갑니다. 하지만 바로 여기서 수학적 장벽에 부딪혔습니다. 만약 한 칸에 유효한 선택지가 두 개 이상 남아 있다면 어떻게 될까요?

논리가 바닥나고 알고리즘이 두 숫자 사이에서 추측을 강요받는 순간, 단일 선형 타임라인(linear timeline)은 분기됩니다. 우리는 다시 $O(n^m)$의 지수적 악몽 속으로 빠져들게 됩니다.

Transformer의 깨달음: 전역적 인식 (Global Awareness)

이 문제를 해결하기 위해서는, 추측에 의존하기 전까지 알고리즘을 가능한 한 오랫동안 선형 상태인 $O(3^m)$에 머물게 할 방법이 필요했습니다.

그때 현대 머신러닝 (Machine Learning)에서 Transformer 아키텍처가 정보를 처리하는 방식이 떠올랐습니다. Transformer는 토큰을 하나씩 순차적으로 읽는 대신, 출력을 생성하기 전에 전체 문맥 (Context)을 전역적으로 주의 깊게 살핍니다 (Attention).

표준 스도쿠 솔버 (Sudoku solver)들은 "국소적으로 눈이 멀어" 있습니다. 이들은 중간에 빈칸이 얼마나 있는지와 상관없이 1행 1열, 그다음 1행 2열을 맹목적으로 처리합니다.

만약 순차적으로 이동하는 대신, 알고리즘이 매 반복 (Iteration)마다 전체 보드 상태를 먼저 매핑한다면 어떨까요? 남은 유효한 선택지가 가장 적은 칸을 찾기 위해 모든 $m$개의 빈칸을 스캔함으로써 (최소 잔여 값 휴리스틱, Minimum Remaining Values heuristic), 우리는 가장 제약이 심한 부분부터 공략할 수 있고, 결정 트리 (Decision tree)가 분기될 기회를 갖기도 전에 이를 붕괴시킬 수 있습니다.

보드 상태를 사전에 매핑하기 위해 $O(m^2 + 3^m)$이라는 작은 다항식 "세금 (Tax)"을 지불하는 것은, 나중에 수백만 개의 막다른 길을 탐색해야 하는 상황을 잠재적으로 방지해 줄 수 있습니다. 이제 이 가설을 Python으로 테스트해 볼 차례입니다.

이론을 Python으로 구현하기 (AI 동료와 함께)

집합 논리 (Set logic)를 설계한 후, 저는 이 가설을 Python 스크립트로 바꾸고 싶었습니다. 그래서 저는 AI 협업자를 사용하여 로직을 구현할 뿐만 아니라, 단 한 줄의 코드가 실행되기 전에 제 가설에 의문을 제기하도록 하기로 결정했습니다.

저는 Gemini 3.1 Pro 터미널을 열고, 제가 세운 집합론 (set theory)을 펼쳐 놓은 뒤 모델에게 제 추론을 스트레스 테스트 (stress-test) 해달라고 요청했습니다. 제가 부분 집합 매핑 (subset mapping)을 통해 전체 실행 시간을 $O(m^2+3m)$의 다항식 경계 (polynomial bound)로 줄일 수 있다고 처음 제안했을 때, 모델은 즉각 반박하며 스도쿠는 NP-완전 (NP-Complete) 문제이며, 적대적인 보드 (adversarial board)의 경우 여전히 $O(n^m)$의 지수적 분기 트리 (exponential branching tree)를 강제할 것이라고 상기시켜 주었습니다.

아이디어를 포기하는 대신, 저는 모델과 대화를 이어갔습니다. 산파술 (Maieutics Socratic method)을 활용하여, 저는 AI에게 제 정확한 사고 과정을 안내했습니다. 즉, 우리가 마법처럼 NP-완전성을 깨뜨리려는 것이 아니라, 실제 상황에서 지수적 탐색 공간 (exponential search space)을 얼마나 제거할 수 있는지를 테스트하려는 것이라고 설명했습니다.

이론적 프레임워크 (theoretical framework)가 일치하자, 저는 모델에게 구현 코드를 생성하도록 요청했습니다:

• 최적화된 MRV 솔버 (The Optimized MRV Solver): 저의 부분 집합 로직, 해시 집합 (hash sets), 그리고 전역 보드 매핑 (global board mapping)을 구현합니다.

def _get_valid_options(self, r, c):
    # 제약 조건 전파 (Constraint Propagation): 3개의 부분 집합을 O(1) 시간에 확인
    options = set(range(1, self.size + 1))
...

• 클래식 백트래커 (The Classic Backtracker): 기준 대조군 (baseline control group)을 설정하기 위한 표준적인 브루트 포스 (brute-force) 솔버입니다.

def _is_valid(self, r, c, val):
    # 단순 검증 (Naive Validation): 해시 집합을 사용하는 대신 배열을 루프하며 확인

...

기계 사양, CPU 클럭 속도, 또는 백그라운드 OS 프로세스와 무관하게 알고리즘의 효율성을 측정하기 위해, 저는 두 솔버 모두에 알고리즘이 마주치는 모든 막다른 길을 추적할 수 있는 backtrack_count 지표를 삽입했습니다.

실증적 결과는 제 예상을 뛰어넘었습니다.

저는 먼저 두 가지 4×4 스도쿠 퍼즐을 사용하여 두 알고리즘의 벤치마킹 (benchmarking)을 시작했습니다. 기본 정확성을 테스트하기 위한 표준 퍼즐 하나와, 빈 보드가 최악의 시나리오 (worst-case scenario)를 강제할 것이라 예상한 빈 보드 하나였습니다.

두 솔버 모두 4×4 퍼즐을 손쉽게 처리하며, 백트래킹 (backtrack) 횟수 0을 기록했습니다. 결과적으로 4×4 그리드는 두 알고리즘 모두에게 깊은 탐색 함정 (search traps)을 만들 만큼 충분히 크지 않았습니다.

코드를 한계까지 밀어붙이기 위해, 저는 9×9 그리드로 규모를 확장했습니다. 저는 빈 9×9 그리드와, 과도한 분기 (branching)를 유발하도록 설계된 악명 높게 어려운 9×9 적대적 퍼즐 (adversarial puzzle)을 대상으로 두 솔버 (solver)를 모두 테스트했습니다.

그 차이는 경이로웠습니다:

• 클래식 솔버 (Classic Solver, Naive Backtracking): 적대적 퍼즐에서 _49,498_번의 백트래킹 (backtracks)을, 빈 그리드에서 _310_번의 백트래킹을 반환했습니다.

• 나의 최적화된 솔버 (My Optimized Solver, MRV + Hash Sets): 적대적 퍼즐에서 _1,608_번의 백트래킹을, 빈 그리드에서 _0_번의 백트래킹을 반환했습니다.

수학적으로 말하자면, 추측하기 전에 제약 조건 (constraints)을 전역적으로 매핑함으로써 적대적 보드에서 지수적 결정 트리 (exponential decision tree)를 96.75% 가지치기 (pruned)했습니다.

빈 보드 현상 (The Empty Board Phenomenon)

빈 보드 결과는 특히 흥미로웠습니다. 왜 나의 알고리즘은 빈 그리드에서 백트래킹 횟수가 0을 기록했을까요?

나의 솔버는 매 반복 (iteration)의 시작 단계에서 최소 잔여 값 (Minimum Remaining Values, MRV)을 사용하여 전체 보드를 매핑하기 때문에, 함정에 빠지는 일이 전혀 없습니다. 원격 모순 (distant contradictions)을 생성할 미리 채워진 숫자가 없으므로, 알고리즘은 단 하나의 막다른 길 (dead end)도 마주치지 않고 유효한 숫자들을 순차적으로 배치하여 "사전식 순서상 첫 번째 (lexicographically first)" 유효한 그리드를 생성합니다.

또한, 저는 결과가 완전히 결정론적 (deterministic)임을 확인하기 위해 동일한 실행을 여러 번 반복하여 두 알고리즘을 실행했습니다. 모든 실행에서 동일한 백트래킹 횟수가 산출되었으며, 이는 성능의 도약이 순수하게 구조적인 것임을 확인시켜 주었습니다.

알고리즘을 테스트하기 위해, 저는 Gemini 3.1 Pro를 사용하여 '쉬움 (Easy)'부터 '17-힌트 적대적 그리드 (17-clue Adversarial grids)'까지 아우르는 10개의 퍼즐 벤치마크 제품군을 구축했습니다. 실증적 데이터는 모든 기대를 뛰어넘었습니다. 해결 가능한 모든 보드에 대해, 최적화된 솔버는 백트래킹 사이클을 평균 98.99% 감소시켰습니다.

처음 _9_개의 퍼즐에서만 클래식 솔버는 _77_백만 개 이상의 막다른 길을 누적한 반면, 최적화된 솔버는 총 _130,000_번의 백트래킹만으로 동일한 보드들을 돌파했습니다.

최종 테스트는 퍼즐 #10에서 이루어졌습니다. 기존 알고리즘은 지수적 탐색 트리 (exponential search tree)에 갇혀 제 Intel i7 CPU에서 60분 이상 실행되다가 제가 프로세스를 강제 종료했습니다. 반면, 보드 제약 조건을 전역적으로 지속적으로 매핑하는 최적화된 알고리즘은 극단적인 그리드를 탐색하여 약 2분 만에 문제를 해결했으며, 단순한 솔버(naive solver)라면 완료하는 데 수 시간이 걸렸을 1,020만 번의 백트래킹 (backtracks)을 정복했습니다.

내가 배운 것들

• 하드웨어는 나쁜 복잡도(Complexity)를 앞지를 수 없다: 지수적 문제에 더 빠른 CPU나 더 큰 클라우드 인스턴스를 투입하는 것은 임시방편일 뿐입니다. 실제로 확장성(scale)을 제공하는 것은 알고리즘의 효율성 (algorithmic efficiency)과 수학적 통찰력입니다.

• 복합적인 최적화 (Compounding Optimizations): O(n) 배열 루프 대신 O(1) 해시 세트 (Hash Sets)를 사용하는 데이터 구조 최적화와, 최소 잔여 값 (Minimum Remaining Values) 휴리스틱 탐색 가지치기 (heuristic search pruning)를 결합하면 거대한 복합 효과가 발생합니다. 알고리즘은 더 적은 결정을 내리게 되고, 내리는 모든 결정의 비용은 무한히 저렴해집니다.

• 실용적인 NP-완전성 (Pragmatic NP-Completeness): 결국 저는 O(nm)이라는 이론적인 최악의 경우 상한선 (worst-case upper bound)을 바꾸지는 못했습니다. 일반적인 스도쿠는 여전히 NP-완전 (NP-Complete) 문제입니다. 하지만 문제의 수학적 제약 조건을 이해함으로써, 저의 최적화된 솔버는 실제 실행 과정에서 계산적 악몽의 _98.99%_를 우회할 수 있었습니다.

• AI는 협력자이지, 신탁(Oracle)이 아니다: 생성형 AI (Generative AI)는 놀라운 문제 해결 가속기이지만, 문제 영역 (problem space)에 대한 깊은 이해 없이 사용하는 것은 역효효과를 낼 수 있습니다. 만약 제가 지수 시간 복잡도 (exponential time complexity)를 극복하는 것이 불가능하다는 LLM의 초기 경고를 그대로 받아들였다면, 이 프로젝트는 서류상으로만 끝났을 것입니다. 인간의 도메인 직관 (domain intuition)이야말로 이론적 한계와 실질적인 최적화 사이의 간극을 메워주는 요소입니다.