design table
백트래킹은 상태, 후보, 제약, 가지치기, 복원을 표로 고정한다
다섯 칸이 모두 채워져야 조건 과잉과 조건 누락을 구분할 수 있다.
state
candidate
prune
| 설계 칸 | 질문 | 예시 |
|---|---|---|
| 상태 | 현재 노드를 무엇으로 표현하는가 | row, path, used, current sum |
| 후보 | 다음에 무엇을 시도할 수 있는가 | 열 후보, 남은 숫자, 남은 문자 |
| 제약 | 후보가 즉시 위반하는 규칙은 무엇인가 | 열/대각선 충돌, 중복 선택 |
| 가지치기 | 남은 후보로도 정답이 불가능한가 | 합 초과, 남은 합 부족 |
| 복원 | 재귀 호출 뒤 무엇을 되돌리는가 | used, path, sum |