Backtracking & State Space Search

1. Overview

백트래킹과 상태 공간 탐색(Backtracking & State Space Search)은 가능한 모든 선택지를 체계적으로 탐험하되, 현재 경로가 해답으로 이어질 수 없다고 판단되는 순간(Pruning, 가지치기)에 즉시 되돌아와(Backtrack) 불필요한 탐색을 폭발적으로 제거하는, 완전 탐색(Brute Force)과 지능적 탐색의 합성 패러다임입니다.

학습자는 n-Queens, 스도쿠(Sudoku), 부분집합 합(Subset Sum) 같은 제약 충족 문제(CSP, Constraint Satisfaction Problem)를 백트래킹 재귀 템플릿(Choose → Explore → Unchoose)으로 해결하는 구조를 뜯어봅니다. 나아가 탐색 공간을 순서 트리(Search Tree)로 모델링하고, 순열/조합 생성, N-Queens 배치, 그래프 컬러링 문제를 통해 가지치기(Pruning)가 최악 O(n!)의 탐색을 실제로 얼마나 단축하는지 해부하여 알고리즘 설계의 심층 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 백트래킹 템플릿 (Backtracking Template): Choose-Explore-Unchoose 3단계, 상태 공간 트리(State Space Tree), 가지치기(Pruning, Constraint Propagation).
• 조합/순열 생성 (Combination & Permutation Generation): 부분집합(Subset), 순열(Permutation), 조합(Combination), 중복 제거(Deduplication).
• 제약 충족 문제 (CSP): N-Queens, 스도쿠(Sudoku), 그래프 컬러링(Graph Coloring), 부분집합 합(Subset Sum).
• 탐색 가지치기 최적화 (Search Pruning): Arc Consistency(AC-3), Forward Checking, MRV(Minimum Remaining Values) 휴리스틱.

Out-of-Scope

• 게임 트리 탐색(Minimax, Alpha-Beta): 두 플레이어 제로섬 게임의 상태 공간 탐색 $\rightarrow$ AI/Game Theory 영역.
• BFS/DFS 그래프 탐색: 그래프 자체 탐색 알고리즘 $\rightarrow$ 04-04-01. Graph Foundations 영역.

Boundaries

• Backtracking vs DP vs Branch-and-Bound: 백트래킹은 실행 불가능 경로를 즉시 제거하며 완전 탐색. DP는 중복 하위 문제 캐싱으로 최적화. Branch-and-Bound는 최적화 문제에서 상한/하한으로 가지를 정리해 최적해를 보장합니다. N-Queens → 백트래킹(완전 탐색, 실행 불가 즉시 Prune). Knapsack → DP(최적화, 최대 가치). TSP 최적 → Branch-and-Bound(최적 보장 필요).

3. Counterexample

• 상태 복원(Unchoose) 누락의 교차 오염 (State Pollution Without Unchoose): N-Queens 백트래킹에서 board[row][col] = 1(퀸 배치) 후 재귀 탐색 호출. 재귀가 실패로 돌아왔을 때 board[row][col] = 0(퀸 제거, Unchoose)을 빠뜨리는 치명적 실수. 이 경우 이전 재귀의 퀸 배치가 남아있어 이후 탐색에서 유효하지 않은 배치를 잘못 유효 판정하거나, 이미 배치된 퀸의 충돌을 잘못 감지하여 실제 해를 건너뛰는 상태 오염(State Pollution)이 발생합니다. Unchoose(상태 복원)는 백트래킹의 절대 불변 계약입니다.
• 가지치기 없는 완전 탐색의 순열 폭발 (Brute Force Permutation Explosion): N=15개의 도시를 방문하는 TSP의 모든 경로를 가지치기 없이 순열로 생성하는 방법: 15! = 1,307,674,368,000 ≈ 1.3조 번의 경로 검사. 10억(10^9) 연산/초 CPU에서 1300초 ≈ 22분이 걸립니다. 가지치기를 적용하면 실제 탐색 경로를 수십~수백 배 줄일 수 있습니다.

4. Prerequisites

• 재귀 (Recursion) (Basic): 백트래킹은 재귀 기반으로, 호출 스택이 상태 복원(Unchoose)의 메커니즘 역할을 합니다. (04-03-01 Recursion)
• 트리와 DFS (Recommended): 상태 공간 트리를 DFS로 탐색하는 개념이 백트래킹의 구조적 기반입니다. (04-04-01 Graph Foundations)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 선택-탐색-취소의 3단계 리듬, 백트래킹 템플릿 (Backtracking Template)

• Why to Learn: "모든 경우의 수를 탐색하되, 막히면 되돌아온다"는 백트래킹의 핵심 리듬(Choose-Explore-Unchoose)을 재귀 코드의 구조로 내면화하여, 어떤 조합 최적화 문제에도 적용 가능한 범용 탐색 근육을 만들기 위함입니다.
• What to Learn:
  • Concepts: Choose(선택), Explore(탐색, 재귀), Unchoose(취소, 상태 복원), 기저 조건(Base: 완전한 해 도달 또는 탐색 공간 소진).
  • Skills: 순열/조합 생성, 중복 원소 처리(정렬+건너뜀), 방문 배열(visited[]).
  • Tools: Python 재귀 + 리스트 상태 관리.
• How to Learn:
  • 1단계: 순열 생성 [1,2,3]의 모든 순열: backtrack(path=[], remaining=[1,2,3]). 기저: remaining == [] → 출력. 루프: 각 원소 x를 path에 추가(Choose), backtrack(path+[x], remaining-[x]) 호출(Explore), 루프 후 자동 복원(Unchoose).
  • 2단계: 조합 생성: 인덱스 start를 도입하여 start 이후 원소만 선택하면 중복 없는 조합(C(n,k))을 생성합니다. [1,2,3,4]에서 크기 2 조합 생성 역학을 뜯어봅니다.
• Implement: 파이썬 permutations(nums) + combinations(nums, k). permutations([1,2,3]) → [1,2,3],[1,3,2],[2,1,3],...] 6개. combinations([1,2,3,4], 2) → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4](./1,2,3],[1,3,2],[2,1,3],...]-6개.-combinations([1,2,3,4],-2)-→-[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4) 6개. Python itertools.permutations/combinations 결과와 assert 비교.

Recommended

Core Topic 02: 체스판의 평화, N-Queens 문제 (N-Queens Problem)

• Why to Learn: N-Queens는 백트래킹의 가장 교과서적인 예시로, 상태 공간 트리의 깊이(N), 가지 수(N), 가지치기 효과를 직관적으로 이해하게 해주며, 레지스터 할당, 스케줄링 제약 등 실무 CSP 문제의 구조적 모델입니다.
• What to Learn:
  • Concepts: N×N 체스판, 행(row)마다 퀸 1개 배치, 열/대각선 충돌 검사.
  • Skills: 충돌 검사를 O(1)로 최적화(열 집합 + 대각선 집합), 모든 해 열거 vs 하나만 탐색.
  • Trade-offs: 충돌 검사를 is_valid(board, row, col) 루프로 O(n) 수행 vs col_set, diag1_set, diag2_set 집합으로 O(1) 수행의 상수 계수 최적화.
• How to Learn:
  • 1단계: row=0부터 각 열(col=0..n-1)을 시도. 현재 위치가 유효하면 퀸 배치(Choose), row+1로 재귀(Explore). row==n이면 완전한 해 도달(기저). 유효하지 않으면 다음 열 시도. 재귀 리턴 후 퀸 제거(Unchoose)하는 N-Queens 역학을 해부합니다.
  • 2단계: 대각선 충돌 조건: / 방향 대각선 row-col 값 동일, \ 방향 row+col 값 동일. 이를 두 집합으로 O(1) 확인하는 최적화를 뜯어봅니다.
• Implement: 파이썬 n_queens(n). col_set, pos_diag_set, neg_diag_set으로 O(1) 충돌 확인. n=8에서 92개의 모든 해 열거 후 카운트 검증. 가지치기 없는 Brute Force(모든 8^8 배치 검사)와 백트래킹의 실제 탐색 노드 수(Visit Count) 비교 로그.

Practical

Core Topic 03: 제약 전파와 빈 칸 채우기, 스도쿠 솔버 (Sudoku Solver)

• Why to Learn: 스도쿠 솔버는 백트래킹과 제약 전파(Constraint Propagation)가 결합된 CSP 해법의 정수이며, AI Planning, 자동화 테스트 케이스 생성, 레지스터 할당 최적화의 구조적 원형입니다.
• What to Learn:
  • Concepts: CSP 변수/도메인/제약 정의, 제약 전파(Constraint Propagation, 한 칸 결정 시 같은 행/열/박스 도메인에서 해당 값 제거), Forward Checking.
  • Skills: MRV(Minimum Remaining Values) 휴리스틱으로 도메인이 가장 작은 빈 칸 먼저 선택.
• How to Learn:
  • 1단계: 빈 칸(0)을 순서대로 탐색. 각 빈 칸에 1~9 중 유효한 값(행/열/3×3 박스 중복 없는)을 시도. 유효하면 채우고(Choose) 다음 빈 칸 재귀(Explore). 해가 없으면 0으로 복원(Unchoose)하고 다음 값 시도하는 역학을 해부합니다.
  • 2단계: 제약 전파 강화: 빈 칸에 값을 채울 때, 같은 행/열/박스의 다른 빈 칸들의 "가능한 값 도메인"에서 해당 값을 즉각 제거합니다. 도메인이 1개로 줄어든 칸은 자동으로 결정(Forward Checking)하여 탐색 필요 없는 칸을 줄이는 가속 역학을 뜯어봅니다.
• Implement: 파이썬 solve_sudoku(board). 빈 칸 탐색 + 1~9 값 시도 백트래킹. 세계에서 가장 어렵다는 스도쿠 퍼즐로 테스트하여 솔버가 해를 찾음을 검증. 단순 백트래킹 vs MRV 휴리스틱 추가 버전의 탐색 횟수(backtracks 카운터) 비교 로그.

Advanced

Core Topic 04: 탐색 공간의 지능적 축소, 가지치기 최적화 (Search Pruning & MRV Heuristics)

• Why to Learn: 단순 백트래킹으로 몇 분 걸리는 CSP 문제를 MRV + Constraint Propagation + Arc Consistency 결합으로 0.1초 안에 해결하는 지능형 탐색 최적화의 핵심을 장악하여 AI Planning, 자동 설정(Auto-configuration) 시스템을 구현하기 위함입니다.
• What to Learn:
  • Concepts: MRV(Minimum Remaining Values, 가장 제약 많은 변수 먼저), LCV(Least Constraining Value, 다른 변수에 최소 영향 값 먼저), Arc Consistency(AC-3 알고리즘).
  • Skills: AC-3으로 전체 CSP 도메인 사전 정리, 백트래킹 전 최대 도메인 축소.
  • Tools: Python constraint 라이브러리.
• How to Learn:
  • 1단계: MRV 휴리스틱: 다음에 배정할 CSP 변수를 선택할 때, 가능한 값이 가장 적은(Most Constrained) 변수를 먼저 선택. 도메인이 작은 변수를 먼저 처리하면 실패(Fail)를 빠르게 탐지하여 불필요한 탐색 트리 전체를 조기에 가지치기합니다.
  • 2단계: AC-3 알고리즘: 모든 아크(Constraint) 쌍 (X, Y)를 큐에 삽입. X의 도메인에서 Y의 어떤 값으로도 제약을 만족할 수 없는 X의 값을 제거. X 도메인 변경 시 X에 연결된 다른 아크를 큐에 추가. 백트래킹 시작 전 전체 도메인을 최대한 줄이는 사전 처리를 해부합니다.
• Implement: 파이썬 Graph_Coloring_Backtracking(graph, colors) 구현. 노드별 인접 노드 목록으로 그래프 표현. 단순 백트래킹 vs MRV(도메인 크기 순 변수 선택) 적용 버전 탐색 횟수 비교. 20개 노드 그래프에서 4색 컬러링 탐색 횟수 감소 효과(%)를 로그로 출력.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Construction / Runtime Efficiency (Search Techniques) — Search strategies.
• [P1] CS2023 - AL/Algorithms and Complexity (Search Paradigms) — Core requirements.

Secondary

• [Artificial Intelligence: A Modern Approach] Russell — CSP and state space depth.
• [The Algorithm Design Manual] Steven Skiena — Backtracking and pruning recipes.

Industry

• [IBM: Constraint Solver for Scheduling] — Real-world industry application.
• [Google: OR-Tools (Constraint Programming)] — Advanced solver implementation.

9. Final Checklist

Primary

• '백트래킹' 과정에서 이전 상태를 복구하기 위해 '상태 관리 배열'이나 '시스템 스택'이 물리적으로 어떻게 사용되는지 설명 가능한가? (P1)
• '가지치기'가 적용된 알고리즘과 적용되지 않은 알고리즘의 탐색 노드 수 차이를 수리적으로 입증할 수 있는 가? (P1)

Secondary

• DFS와 백트래킹의 관계가 왜 시스템 자원(재귀 깊이)의 물리적 한계와 직결되는지 소통 가능한가?
• 주어진 문제의 제약 조건을 이용해 '유망성 함수'를 설계하고 이를 코드로 옮기는 과정을 도출할 수 있는 가?

Industry

• 배송 경로 최적화나 물류 관리 솔루션 설계 시, 백트래킹 기반의 CSP 기법이 왜 물리적 표준 인프라인지 기술할 수 있는 가? (SFIA)
• 대용량 퍼즐 게임 서버에서 수천 명의 동시 요청을 처리하기 위해 탐색 트리의 깊이를 제한하는 'Iterative Deepening'의 물리적 필요성을 제안할 수 있는 가?