[파이썬] 백 트래킹(Backtracking) 기법

• 제약조건 만족 문제(Constraint Satisfaction Problem)에서 해를 찾기 위한 전략
  
  • 해를 찾기 위해 후보군에서 제약조건을 점진적으로 검사하다가, 해당 후보군이 제약조건을 만족할 수 없다고 판단되면 더 이상 연관된 후보들을 검사하지 않고 다른 후보군으로 넘어가 최적의 해를 찾음

 

• 실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)을 상태공간트리(State Space Tree)를 통해 표현함
  • 각 후보군을 DFS 또는 BFS 방식으로 확인
  • Promising : 해당 후보군이 조건에 맞는지 검사
  • Pruning(가지 치기) : 조건에 맞지 않으면, 바로 다른 후보군으로 넘어가 탐색 시간을 절약함

 

(예제) N Queen 문제 - NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제

N Queen 문제의 이해

 

1. 한 행에는 하나의 퀸만 배치할 수 있으므로, 맨 위의 행부터 퀸을 배치하고 다음 행에 퀸을 배치할 수 있는 위치를 찾아 배치함
2. 이전까지 배치한 퀸에 의해 현재 행에 퀸을 배치할 위치가 없다면, 이전 행의 퀸의 위치를 바꿈
3. 위 과정을 반복해서 모두 만족하는 해를 찾음

(왼쪽) 해를 찾는 과정에서의 상태공간트리 일부분, (오른쪽) 찾아낸 해의 위치

 

후보군이 될 수 없는 조건을 검사하는 기법(Promising)

 

< 파이썬 코드로 구현 >