백트래킹(Backtracking)은 가능한 모든 경우를 탐색하되, 유망하지 않은 경로는 일찍 포기(가지치기) 하는 알고리즘 기법이다. 완전 탐색보다 효율적이며, N-Queens, 스도쿠, 순열·조합 생성에 활용된다.
기본 구조
python
def backtrack(state, candidates):
if is_solution(state):
process_solution(state)
return
for candidate in candidates:
if is_valid(state, candidate):
state.append(candidate) # 선택
backtrack(state, ...) # 재귀
state.pop() # 취소 (백트래킹)
N-Queens 문제
python
def solve_n_queens(n):
solutions = []
queens = [] # queens[i] = i행에서 퀸의 열 위치
def is_valid(row, col):
for r, c in enumerate(queens):
if c == col or abs(r - row) == abs(c - col):
return False
return True
def backtrack(row):
if row == n:
solutions.append(queens[:])
return
for col in range(n):
if is_valid(row, col):
queens.append(col)
backtrack(row + 1)
queens.pop()
backtrack(0)
return len(solutions)
print(solve_n_queens(8)) # 92
관련 개념
참고문헌
- •Skiena, S. The Algorithm Design Manual
