Skip to content

LLM은 왜 스도쿠와 지뢰찾기에서 갑자기 틀리는가: 무도구 텍스트 생성 조건에서의 제약 추적 한계

핵심 요약

LLM이 스도쿠·지뢰찾기 같은 퍼즐에서 초반에는 그럴듯하게 풀다가 특정 단계부터 틀리는 현상은, 겉보기에는 “갑작스러운 오류”처럼 보이지만 실제로는 중간 상태 추적 오류가 누적되다가 어느 순간 표면화되는 경우가 많다. 핵심 원인은 퍼즐이 요구하는 계산 구조와 무도구 텍스트 생성 조건의 LLM이 기본적으로 수행하는 작업 구조가 다르다는 데 있다.

스도쿠와 지뢰찾기는 넓은 의미에서 제약 만족 문제(CSP, Constraint Satisfaction Problem)의 성격을 가진다. 스도쿠에서는 행·열·3×3 블록 제약을 동시에 만족해야 하고, 지뢰찾기에서는 숫자 칸이 주변 지뢰 개수에 대한 제약을 제공한다. 이런 문제를 안정적으로 풀려면 현재 보드 상태, 후보 집합, 확정값, 가정, 모순, 되돌림 지점을 명시적으로 저장하고 갱신해야 한다.

기본적인 무도구 텍스트 생성 설정에서 LLM은 퍼즐 전용 보드 자료구조, 후보 집합 테이블, 제약 전파기, 백트래킹 탐색기를 자동으로 갖고 있는 시스템으로 보기 어렵다. 모델은 문맥 안의 정보를 활용해 국소적으로 타당해 보이는 풀이 서술을 만들 수 있지만, 그 서술이 항상 실제 후보 집합 계산, 좌표 검산, 전역 제약 검사를 동반한다고 보장되지는 않는다.

따라서 이 글의 중심 주장은 다음과 같다. LLM이 퍼즐에서 틀리는 이유는 “논리를 전혀 모른다”는 단순한 결론이 아니라, 무도구 텍스트 생성 조건에서 장기 상태 유지, 다중 제약의 동시 갱신, 오류 발생 시 정확한 되돌림, 좌표·후보 집합의 엄밀한 검산이 불안정해질 수 있기 때문이다. 도구 보강 LLM, 코드 실행기, 제약 solver, 외부 상태표를 결합하면 이 한계는 상당히 완화될 수 있다.

문제의식

스도쿠와 지뢰찾기는 대중적 퍼즐이지만, AI의 추론 능력을 관찰하기에 매우 좋은 시험장이다. 두 퍼즐은 대규모 배경지식을 요구하지 않는다. 문제를 풀기 위해 역사적 사실, 사회 상식, 문학적 해석, 전문 데이터베이스가 필요한 것은 아니다. 규칙은 비교적 짧게 설명할 수 있고, 정답 검증도 명확하다. 그래서 이런 퍼즐은 모델이 정말로 현재 상태를 읽고, 제약을 보존하고, 여러 조건을 결합하고, 모순을 발견하며, 필요한 경우 이전 판단을 수정할 수 있는지를 드러낸다.

일상적인 질의응답에서는 LLM의 약한 오류가 잘 보이지 않을 때가 많다. 문장이 조금 부정확해도 전체 뜻이 유지될 수 있고, 요약이 다소 느슨해도 사용자는 큰 흐름을 이해할 수 있다. 퍼즐은 이런 관용을 거의 허용하지 않는다. 스도쿠에서 숫자 하나를 잘못 넣으면 같은 행·열·블록의 후보 구조가 모두 바뀐다. 지뢰찾기에서 주변 8칸 중 하나를 빠뜨리면 지뢰 후보와 안전 칸 판단이 달라진다.

이 때문에 사용자는 LLM이 쉬운 단계에서는 잘 풀다가 어느 순간 “갑자기” 틀린다고 느낀다. 실제로는 갑작스러운 단절이라기보다 이전 단계의 작은 불일치가 누적되어 특정 추론 단계에서 드러나는 경우가 많다. 초반에는 국소 규칙만으로도 답을 낼 수 있지만, 난도가 올라가면 보드 전체의 후보 구조와 제약 관계를 장시간 유지해야 한다. 바로 이 지점에서 무도구 텍스트 생성 조건의 LLM은 퍼즐 전용 알고리즘과 구별되는 한계를 보인다.

개념의 정의

스도쿠와 지뢰찾기를 이해하려면 먼저 제약 만족 문제라는 개념을 잡아야 한다. 제약 만족 문제는 변수, 가능한 값, 그리고 변수들 사이의 제약으로 구성된다. 목표는 모든 제약을 동시에 만족하는 값을 찾는 것이다. 스도쿠에서는 각 빈칸이 변수이고, 1부터 9까지의 숫자가 가능한 값이며, 행·열·3×3 블록에 같은 숫자가 반복되지 않아야 한다는 조건이 제약이다. 지뢰찾기에서는 각 닫힌 칸이 지뢰인지 아닌지가 변수이고, 열린 숫자 칸은 주변 8칸에 포함된 지뢰 수라는 제약을 제공한다.

제약 추적은 단순히 규칙을 아는 일이 아니다. 현재 상태에서 어떤 제약이 어느 변수에 적용되는지, 어떤 후보가 제거되었는지, 어떤 가정이 아직 유효한지 계속 갱신하는 능력이다. 스도쿠에서 한 칸에 5가 확정되면 같은 행·열·블록에 있는 다른 칸의 후보에서 5가 제거된다. 그 제거는 다른 칸의 후보를 하나로 줄일 수 있고, 다시 새로운 확정값을 만든다. 지뢰찾기에서도 어떤 칸을 지뢰로 표시하면 주변 숫자 칸들의 남은 지뢰 수가 바뀌고, 그 변화는 안전 칸과 추가 지뢰 후보를 다시 결정한다.

상태 갱신은 제약 추적의 기반이다. 여기서 상태란 화면에 보이는 현재 보드만 뜻하지 않는다. 확정값, 후보값, 배제된 후보, 이미 사용한 가정, 모순이 발생한 분기, 아직 확인하지 않은 주변 칸, 전체 남은 지뢰 수 같은 정보까지 포함한다. 사람은 종이에 후보 숫자를 적거나 머릿속으로 보드 구조를 유지한다. 전통적 알고리즘은 배열, 집합, 그래프, 제약 테이블, 탐색 트리 같은 명시적 자료구조를 사용한다.

LLM의 문맥 활용 능력은 이런 상태 갱신과 혼동되기 쉽다. Transformer 기반 모델은 현재 문맥을 반영한 내부 활성 상태를 만들고, attention을 통해 이전 토큰의 정보를 활용한다. 일부 제품형 AI 시스템은 대화 기억, 파일, 검색, 코드 실행, 외부 도구를 결합하기도 한다. 이 글에서 말하는 한계는 그런 확장 시스템 전체가 아니라, 주로 외부 도구와 명시적 상태표 없이 텍스트만 입력받고 텍스트만 출력하는 조건을 가리킨다. 이 조건에서 LLM의 내부 활성값은 퍼즐 풀이 프로그램이 사용하는 안정적이고 검증 가능한 보드 상태 저장소와 같은 역할을 한다고 보기 어렵다.

배경과 맥락

Transformer 기반 언어모델의 기본 출력 구조는 다음 토큰 예측이다. 「Attention Is All You Need」는 Transformer가 입력·출력 토큰을 벡터로 변환하고, 디코더 출력에 선형 변환과 softmax를 적용해 다음 토큰 확률을 만든다고 설명한다. 이 구조는 긴 문맥 안의 언어적 의존성을 학습하는 데 강력하지만, 특정 퍼즐의 후보 집합을 별도 자료구조에 저장하고 제약 전파를 반복 수행하는 전통적 CSP solver와 동일한 방식으로 작동하지 않는다.

고전적 CSP 풀이에서는 상태가 명시적으로 표현된다. 스도쿠 풀이 프로그램은 각 칸의 후보 숫자 집합을 유지하고, 숫자 하나가 확정될 때마다 관련 행·열·블록의 후보를 갱신한다. 더 어려운 경우에는 백트래킹을 사용한다. 하나의 값을 가정하고 진행하다가 모순이 발생하면 이전 선택 지점으로 돌아가 다른 값을 시도한다. 이 과정에서 중요한 점은 오류가 발생했을 때 어느 선택에서 오류가 시작되었는지를 추적할 수 있다는 것이다.

LLM도 자연어로 “가정해 보자”, “모순이 생긴다”, “따라서 되돌아간다”는 문장을 만들 수 있다. 그러나 그런 문장을 생성하는 것과 실제 탐색 트리의 노드를 보존하고 복구하는 것은 구분되어야 한다. 모델이 코드 실행기, 외부 메모리, 검증기, solver를 사용하지 않는다면, 백트래킹은 텍스트 안의 서술로만 나타날 수 있다. 작은 문제에서는 이 서술이 실제 풀이와 잘 맞아 보인다. 상태 수가 늘어나고 제약이 얽히면 텍스트 기반 서술과 명시적 계산 사이의 차이가 커진다.

최근 연구들도 이 차이를 여러 방식으로 관찰한다. Li, Wang, Zhang의 NAACL 2024 논문 「Assessing Logical Puzzle Solving in Large Language Models: Insights from a Minesweeper Case Study」는 지뢰찾기를 LLM의 논리 퍼즐 풀이 능력 평가 사례로 사용했다. 이 연구는 보드 내비게이션, 주변 칸 세기, 상태 이해, 공간 관계 파악 같은 하위 능력이 지뢰찾기 풀이에 중요하며, 보드 표현 방식에 따라 성능 차이가 나타날 수 있음을 보여준다.

Chen, Wei, Ren, Li, Zhang의 ACL 2025 Findings 논문 「LR²Bench」는 스도쿠를 포함한 여러 제약 만족 문제를 사용해 긴 사슬의 반성적 추론 능력을 평가한다. 이 논문은 LR²Bench가 Crossword, Acrostic, Logic Puzzle, Cryptogram, Sudoku, Drop의 여섯 종류 CSP 과제로 구성된다고 설명한다. 논문은 o1-like reasoning model이 가정, 검증, 백트래킹, 자기수정을 더 잘 수행할 수 있다는 가능성을 전제하면서도, 평가 결과에는 여전히 상당한 개선 여지가 있다고 보고한다.

Seely, Imajuku, Zhao, Cetin, Jones의 2025년 「Sudoku-Bench」는 변형 스도쿠를 통해 창의적·다단계 논리 추론을 평가한다. 이 벤치마크는 각 퍼즐이 고유하거나 미묘하게 상호작용하는 제약을 갖도록 구성되어 있어, 단순한 암기나 표준 풀이 패턴으로 해결하기 어렵다는 점을 강조한다. 해당 논문은 발표 당시 평가한 state-of-the-art LLM들이 도구 없이 푼 경우 전체 퍼즐의 15% 미만만 해결했다고 보고한다. 이 수치는 모든 미래 모델의 한계를 의미하지 않으며, 특정 벤치마크와 평가 조건에서 관찰된 결과로 이해해야 한다.

핵심 논리

LLM이 스도쿠와 지뢰찾기에서 틀리는 첫 번째 이유는 상태가 명시적 자료구조가 아니라 텍스트 문맥 안에 분산되어 있기 때문이다. 퍼즐 풀이에서는 현재 보드가 계속 변한다. 특정 칸이 확정되고, 어떤 후보가 제거되고, 어떤 칸이 지뢰로 표시되고, 어떤 숫자 칸의 남은 지뢰 수가 줄어든다. 프로그램이라면 이런 변화를 테이블이나 집합에 즉시 반영한다. 무도구 LLM은 대화 문맥과 생성 중인 설명에서 이 변화를 추론해야 한다. 보드가 짧고 변화가 적으면 이 방식도 작동할 수 있다. 보드가 길고 여러 단계의 수정이 쌓이면 이전 상태와 현재 상태가 섞일 위험이 커진다.

두 번째 이유는 국소적으로 그럴듯한 판단이 전역적으로는 틀릴 수 있다는 점이다. 스도쿠에서 “이 행에 7이 없으므로 이 칸에 7이 가능하다”는 판단은 행 제약만 보면 맞을 수 있다. 그러나 같은 칸이 속한 열이나 3×3 블록에 이미 7이 있다면 불가능하다. 지뢰찾기에서도 “숫자 1 옆에 닫힌 칸이 하나 남았으므로 그 칸은 지뢰다”라는 규칙은 특정 조건에서만 맞다. 주변 닫힌 칸 수, 이미 표시된 지뢰 수, 인접한 다른 숫자 칸과의 관계를 함께 계산해야 한다.

세 번째 이유는 자동회귀 생성의 누적 오류이다. LLM은 보통 완성된 탐색 결과를 내부에서 전부 계산한 뒤 출력하기보다, 이전 토큰들을 조건으로 다음 토큰을 이어 가는 방식으로 답변을 만든다. 앞부분에서 잘못된 후보를 확정하면 뒤의 문장들은 그 잘못된 전제를 자연스럽게 이어받을 수 있다. 인간 풀이자는 중간에 모순을 발견하면 앞의 가정을 지우고 다시 시작할 수 있다. 전통적 알고리즘은 백트래킹으로 이전 상태를 복구한다. LLM도 자기수정 문장을 생성할 수 있지만, 외부 검증 없이 모든 중간 제약을 다시 계산하는 일은 불안정할 수 있다.

네 번째 이유는 보드 표현 자체가 계산 부담을 준다는 점이다. 사람은 스도쿠나 지뢰찾기 보드를 시각적으로 본다. 행, 열, 블록, 주변 8칸의 관계가 공간적으로 드러난다. 텍스트로 보드를 표현하면 이 관계가 문자열 안에 흩어진다. 좌표 표기, 표 형식, 쉼표 구분, 행렬 표기 방식에 따라 모델이 읽어야 하는 구조가 달라진다. 같은 퍼즐이라도 입력 표현이 불안정하면 모델은 문제 자체보다 보드를 읽는 데서 먼저 오류를 낼 수 있다.

다섯 번째 이유는 퍼즐이 정답뿐 아니라 과정의 엄밀성을 요구한다는 점이다. 자연어 답변에서는 부분적으로 애매한 표현도 전체 의미를 전달할 수 있다. 퍼즐에서는 작은 오류 하나가 전체 해답을 무너뜨린다. 스도쿠에서 한 칸에 잘못된 숫자를 넣으면 이후 후보 제거가 전부 틀어진다. 지뢰찾기에서 지뢰가 아닌 칸을 지뢰로 표시하면 주변 모든 숫자 제약의 해석이 바뀐다. 이 낮은 오류 허용도가 LLM의 약점을 크게 드러낸다.

구체적 사례

스도쿠의 간단한 예를 보자. 어떤 빈칸 A가 있고, A가 속한 행에는 1, 2, 3, 4가 이미 있으며, A가 속한 열에는 5, 6이 있고, A가 속한 3×3 블록에는 7, 8이 있다고 하자. 그러면 A의 후보는 9 하나만 남는다. 이 상황은 국소적으로 단순하다. LLM도 이런 규칙을 자연어로 잘 설명할 수 있다.

문제는 후보가 여러 칸 사이에서 얽힐 때 나타난다. 예컨대 한 행의 두 칸 A와 B가 모두 {2, 5}만 가능하다고 하자. 이 경우 A와 B는 그 행에서 2와 5를 점유하는 쌍이 된다. 같은 행의 다른 칸 C가 겉보기에는 2를 가질 수 있어 보여도, 실제로는 A와 B의 후보쌍 때문에 C에서 2가 제거될 수 있다. 이 판단은 한 칸만 보는 규칙으로는 나오지 않는다. 후보 집합 사이의 관계를 비교하고, 그 관계를 다른 칸 후보에 반영해야 한다.

지뢰찾기에서도 유사한 구조가 있다. 어떤 숫자 1 주변에 닫힌 칸 X와 Y가 있고, 인접한 숫자 2 주변에는 X, Y와 함께 Z가 있다고 하자. 첫 번째 숫자 1은 X와 Y 중 하나가 지뢰라는 제약을 준다. 두 번째 숫자 2는 X, Y, Z 중 두 개가 지뢰라는 제약을 준다. 두 제약을 결합하면 Z가 지뢰라는 결론이 나올 수 있다. 이 결론은 숫자 하나만 보아서는 나오지 않는다. 두 숫자가 가리키는 주변 칸 집합을 비교해야 한다.

이런 사례는 왜 오류가 특정 단계에서 드러나는지를 보여준다. 쉬운 단계에서는 “숫자 옆에 닫힌 칸이 하나 남았다”, “이 행에서 남은 숫자는 하나다” 같은 국소 규칙만으로 충분하다. 어려운 단계에서는 여러 숫자·칸·후보 집합의 관계를 동시에 유지해야 한다. 무도구 LLM은 국소적으로 그럴듯한 풀이 서술을 생성할 수 있지만, 그 서술이 실제 집합 연산과 좌표 검산을 매번 안정적으로 수행한다고 단정하기 어렵다.

모델별·인터페이스별 차이

이 주제를 설명할 때 가장 조심해야 할 점은 “LLM 일반론”과 “특정 사용 조건”을 구분하는 것이다. GPT 계열, Claude 계열, Gemini 계열, o-series reasoning model, DeepSeek-R1류 reasoning model, tool-augmented agent는 같은 층위에서 평가하기 어렵다. 모델 구조, 학습 방식, 추론 시간, 자기검토 능력, 컨텍스트 처리 방식, 도구 사용 가능 여부, 입력 표현 형식이 모두 성능에 영향을 준다.

일반적인 채팅형 LLM이 텍스트만 보고 텍스트만 출력하는 조건에서는 보드 상태를 명시적으로 저장하고 갱신하는 장치가 제한적이다. 반면 도구 보강 agent는 Python 코드, SAT solver, constraint solver, 외부 파일, 스프레드시트, 게임 엔진을 사용할 수 있다. 이 경우 LLM은 모든 칸을 직접 계산하는 주체가 아니라, 문제를 형식화하고, 도구를 호출하고, 결과를 해석하는 조정자 역할을 맡을 수 있다. 실패 원인도 “모델이 제약을 추적하지 못했다”에서 “문제를 잘못 형식화했다”, “도구 결과를 잘못 해석했다”, “검증 루프가 부족했다”로 이동한다.

reasoning model도 별도로 봐야 한다. reasoning model은 더 긴 중간 추론, 자기검토, 재시도, 반성적 풀이에서 일반 모델보다 나은 성능을 보이는 경우가 있다. LR²Bench가 주목하는 것도 바로 이런 긴 사슬의 반성적 추론이다. 그러나 긴 추론이 곧 안정적인 상태표를 의미하지는 않는다. 추론을 길게 쓰면 오류를 발견할 기회가 늘 수 있지만, 잘못된 가정을 더 길게 정당화할 가능성도 함께 생긴다.

Apple Machine Learning Research의 「The Illusion of Thinking」은 통제된 퍼즐 환경에서 문제 복잡도가 높아질 때 reasoning model의 성능 붕괴와 reasoning effort의 변화가 나타날 수 있음을 보고했다. 이 연구에는 후속 반론도 있다. Khan, Madhavan, Natarajan의 코멘트는 이를 정적·도구 없는 텍스트 인터페이스가 만든 “agentic gap”으로 재해석한다. 즉 reasoning model의 한계를 모델 내부 능력의 본질적 결핍으로만 볼 것이 아니라, 도구 사용 제한, 인터페이스, 출력 길이, 실행 환경의 제약과 함께 봐야 한다는 것이다. 이 글도 그 입장을 반영하여, 퍼즐 실패를 모든 reasoning model의 본질적 한계로 일반화하지 않는다.

주요 쟁점과 반론

첫 번째 쟁점은 “LLM은 알고리즘을 실행하지 않는다”는 표현의 범위이다. 이 표현은 무도구 텍스트 생성 조건에서는 설명력이 있다. 모델은 퍼즐 풀이 프로그램처럼 후보 집합을 명시적으로 저장하고, 제약 전파를 반복하고, 탐색 트리를 복구하는 장치를 기본 출력 과정에 포함한다고 보기 어렵다. 하지만 모델이 코드 실행 도구를 사용할 수 있다면 이야기는 달라진다. LLM은 Python으로 백트래킹 solver를 작성하고, 그 solver를 실행하여 정답을 얻을 수 있다. 이 경우 LLM은 알고리즘을 직접 내장한 solver라기보다 알고리즘을 구성하고 호출하는 인터페이스로 기능한다.

두 번째 쟁점은 “패턴 기반”이라는 설명의 정확성이다. LLM을 단순한 표면 문자열 통계 장치로만 설명하면 부정확하다. 대규모 학습과 Transformer 구조를 통해 모델은 추상적 규칙, 문맥 관계, 코드 구조, 수학적 풀이 양식, 문제 해결 절차를 상당 부분 학습할 수 있다. 따라서 “패턴 기반”이라는 말은 “아무 계산도 하지 않는다”는 뜻으로 쓰면 안 된다. 더 안전한 표현은 다음과 같다. LLM은 국소적으로 타당해 보이는 풀이 서술을 생성할 수 있지만, 그 서술이 항상 실제 후보 집합 계산이나 좌표 검산을 동반한다고 보장되지는 않는다.

세 번째 쟁점은 퍼즐 난도와 입력 형식이다. 같은 스도쿠라도 사람에게 어려운 문제와 기계에게 어려운 문제는 다를 수 있다. 사람은 시각적 배열에서 쉽게 보는 관계를 텍스트 모델은 놓칠 수 있고, 반대로 사람이 귀찮아하는 반복 계산은 프로그램에게 쉽다. 지뢰찾기도 모든 국면이 순수 논리로 결정되지는 않는다. 정보가 부족한 상태에서는 확률적 선택이 필요할 수 있다. 따라서 모델의 실패를 평가할 때는 해당 퍼즐이 논리적으로 결정 가능한지, 추측이 필요한지, 보드 표현이 일관적인지, 평가가 최종 정답만 보는지 과정 오류도 보는지 구분해야 한다.

네 번째 쟁점은 벤치마크 수치의 일반화이다. Sudoku-Bench의 “15% 미만” 결과는 해당 논문의 특정 퍼즐 집합, 평가 당시 모델군, 도구 없는 조건, 텍스트 기반 표현에서 나온 결과다. 이 수치를 “현재와 미래의 모든 AI는 스도쿠를 못 푼다”는 주장으로 확장하면 과잉 일반화가 된다. 벤치마크 결과는 특정 조건에서 어떤 종류의 능력이 취약하게 드러나는지 보여주는 자료로 읽어야 한다.

오해와 한계

가장 흔한 오해는 LLM이 퍼즐을 틀리면 “추론 능력이 전혀 없다”고 결론내리는 것이다. 퍼즐 실패는 추론 능력의 부재보다 특정 종류의 추론, 특히 정확한 상태 유지와 다중 제약 갱신에서의 취약성을 보여준다. LLM은 규칙 설명, 풀이 전략 제안, 간단한 후보 제거, 오류 가능성 점검에서 유용할 수 있다. 실패가 두드러지는 지점은 정확한 좌표 계산과 전역 일관성 유지가 장시간 요구되는 단계이다.

또 다른 오해는 chain-of-thought를 길게 쓰면 문제가 해결된다는 생각이다. 중간 풀이를 길게 쓰면 모델이 규칙을 더 많이 검토할 수 있고, 쉬운 오류를 줄일 수 있다. 그러나 길어진 텍스트 자체가 안정적인 상태 저장소가 되지는 않는다. 상태가 표, 집합, 코드 변수, 검증 함수로 관리되지 않으면 긴 설명은 오류를 줄이는 장치가 아니라 오류가 누적되는 공간이 될 수도 있다.

세 번째 오해는 “스도쿠는 단순한 퍼즐이므로 AI에게 쉬워야 한다”는 판단이다. 스도쿠의 규칙은 단순하지만, 난도가 높은 문제는 후보 집합의 전역 구조, 가정과 모순 검증, 장거리 의존성을 요구한다. 규칙의 단순성과 풀이의 단순성은 다르다. 지뢰찾기도 숫자의 의미는 간단하지만, 여러 숫자의 주변 집합을 결합하면 조합적 추론 문제가 된다.

네 번째 오해는 “LLM이 내부 메모리가 없다”는 표현을 문자 그대로 이해하는 것이다. Transformer는 현재 문맥을 처리하는 내부 활성 상태를 갖고 있고, attention을 통해 이전 토큰 정보를 참조한다. 일부 시스템은 대화 기억, 검색, 파일, 코드 실행, 외부 도구를 갖기도 한다. 이 글의 핵심은 일반적인 무도구 텍스트 생성 조건의 LLM이 퍼즐 풀이 알고리즘처럼 안정적으로 읽고 쓰고 검증할 수 있는 명시적 보드 상태를 기본적으로 유지하지 않는다는 점이다.

이 설명에는 한계도 있다. 모델 내부 표현을 직접 관찰하기는 어렵다. 어떤 답변이 실제 후보 계산에서 나온 것인지, 학습된 풀이 패턴에서 나온 것인지, 두 요소가 섞인 것인지 단정하기 어렵다. 또한 최신 reasoning model과 tool-augmented agent는 일반 채팅형 LLM과 다른 성능을 보일 수 있다. 공개 벤치마크 결과도 입력 형식, 프롬프트, 샘플링 설정, 출력 길이, 훈련 데이터 오염 가능성, 검증 방식의 영향을 받는다.

개선 방향

LLM이 퍼즐을 더 안정적으로 풀게 하려면 단순히 “더 천천히 생각하라”고 지시하는 것만으로는 부족하다. 핵심은 상태와 검증을 외부화하는 것이다. 스도쿠라면 각 칸의 후보 집합을 표로 만들고, 숫자가 확정될 때마다 후보 제거를 자동 수행해야 한다. 지뢰찾기라면 각 숫자 칸의 주변 닫힌 칸 집합과 남은 지뢰 수를 별도 목록으로 관리해야 한다. 이런 구조는 텍스트 설명을 계산 가능한 상태 표현으로 바꾼다.

두 번째 개선 방향은 검증 루프이다. LLM이 다음 수를 제안하면 별도 검증기가 행·열·블록 제약이나 지뢰 개수 제약을 확인한다. 오류가 있으면 모델에게 단순히 “틀렸다”고 말하는 대신 어떤 좌표에서 어떤 제약을 위반했는지 알려주어야 한다. 그러면 모델은 자연어 추론 생성기 역할을 하고, 외부 검증기는 정확성 보증 장치가 된다.

세 번째 개선 방향은 도구 사용이다. 퍼즐이 CSP라면 constraint solver, SAT solver, Python 백트래킹 코드, 전용 게임 엔진을 연결할 수 있다. 이때 LLM의 역할은 모든 칸을 직접 계산하는 것이 아니라 문제를 올바르게 형식화하고, solver 결과를 해석하고, 사람에게 이해 가능한 설명으로 번역하는 쪽에 가까워진다.

네 번째 개선 방향은 평가 방식의 정교화이다. 모델이 최종 정답을 맞혔는지만 볼 것이 아니라, 보드 읽기, 주변 칸 세기, 후보 제거, 가정 설정, 모순 탐지, 백트래킹, 최종 검증을 단계별로 나누어 평가해야 한다. 그래야 모델이 어디서 실패하는지 구체적으로 파악할 수 있다. 지뢰찾기 논문이 보드 내비게이션과 주변 칸 세기 같은 하위 능력을 분리해 본 것은 이런 평가 관점에서 의미가 있다.

정리

LLM이 스도쿠와 지뢰찾기에서 갑자기 틀리는 이유는 퍼즐이 요구하는 계산 구조와 무도구 텍스트 생성 조건의 LLM이 기본적으로 수행하는 생성 구조 사이의 불일치에서 나온다. 퍼즐은 안정적인 상태 저장, 전역 제약의 동시 적용, 오류 발생 시 되돌아가는 탐색, 작은 좌표 계산의 정확성을 요구한다. LLM은 언어 패턴과 문맥 정보를 활용해 그럴듯한 풀이를 만들 수 있지만, 외부 도구 없이 퍼즐 풀이 프로그램처럼 보드 상태를 명시적으로 저장하고 갱신한다고 보기는 어렵다.

핵심은 세 가지로 압축된다. 첫째, 현재 보드 상태가 텍스트 문맥 안에 분산되므로 상태 추적이 불안정해질 수 있다. 둘째, 쉬운 국소 규칙은 잘 처리해도 여러 제약이 얽힌 전역 일관성 유지에는 약해질 수 있다. 셋째, 중간 오류가 한 번 생기면 자동회귀 생성 과정에서 그 오류가 뒤의 풀이로 전파되기 쉽다.

따라서 퍼즐 풀이에서 LLM을 신뢰하려면 모델 단독 응답보다 구조화된 상태표, 외부 검증기, 코드 실행, 제약 solver, 단계별 검산 루프를 결합하는 편이 안정적이다. 스도쿠와 지뢰찾기는 LLM이 “전혀 추론하지 못한다”는 증거라기보다, 언어적 추론과 계산적 제약 추적이 얼마나 다른 능력인지를 보여주는 선명한 사례이다.

참고자료

  • Vaswani, Ashish, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin, 「Attention Is All You Need」, NeurIPS, 2017. URL: https://papers.neurips.cc/paper/7181-attention-is-all-you-need
  • Russell, Stuart J. and Peter Norvig, 「Artificial Intelligence: A Modern Approach」, Pearson, 4th ed., 2020.
  • Dechter, Rina, 「Constraint Processing」, Morgan Kaufmann, 2003.
  • Li, Yinghao, Haorui Wang, and Chao Zhang, 「Assessing Logical Puzzle Solving in Large Language Models: Insights from a Minesweeper Case Study」, Proceedings of NAACL 2024, Association for Computational Linguistics, pages 59–81, 2024. DOI: 10.18653/v1/2024.naacl-long.4. URL: https://aclanthology.org/2024.naacl-long.4/
  • Chen, Jianghao, Zhenlin Wei, Zhenjiang Ren, Ziyong Li, and Jiajun Zhang, 「LR²Bench: Evaluating Long-chain Reflective Reasoning Capabilities of Large Language Models via Constraint Satisfaction Problems」, Findings of ACL 2025, Association for Computational Linguistics, pages 6006–6032, 2025. DOI: 10.18653/v1/2025.findings-acl.312. URL: https://aclanthology.org/2025.findings-acl.312/
  • Seely, Jeffrey, Yuki Imajuku, Tianyu Zhao, Edoardo Cetin, and Llion Jones, 「Sudoku-Bench: Evaluating Creative Reasoning with Sudoku Variants」, arXiv:2505.16135, 2025. URL: https://arxiv.org/abs/2505.16135
  • Shojaee, Parshin, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, and Mehrdad Farajtabar, 「The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity」, Apple Machine Learning Research, 2025. URL: https://machinelearning.apple.com/research/illusion-of-thinking
  • Khan, Sheraz, Subha Madhavan, and Kannan Natarajan, 「A Comment On ‘The Illusion of Thinking’: Reframing the Reasoning Cliff as an Agentic Gap」, arXiv:2506.18957, 2025. URL: https://arxiv.org/abs/2506.18957
  • Dellibarda Varela, Iñaki, Pablo Romero-Sorozabal, Eduardo Rocon, and Manuel Cebrian, 「Rethinking the Illusion of Thinking」, arXiv:2507.01231, 2025. URL: https://arxiv.org/abs/2507.01231
  • Giadikiaroglou, Panagiotis et al., 「Puzzle Solving using Reasoning of Large Language Models: A Survey」, Proceedings of EMNLP 2024, Association for Computational Linguistics, 2024.