backtracking

가지치기 안전성 판정표

정답 경로를 보존하면서 탐색 노드를 줄이기 위해 재귀 호출 전후로 확인할 기준을 정리합니다.

판정 순서

현재 선택, 인덱스, 사용 집합처럼 노드를 식별하는 정보를 고정합니다.

다음에 선택할 후보가 중복 없이 생성되는지 확인합니다.

부분 상태만으로 위반 여부를 판단할 수 있는 조건을 찾습니다.

정답 가능성이 사라진 분기만 중단하고 나머지는 남겨 둡니다.

재귀가 끝난 뒤 추가한 선택과 사용 표시를 원래대로 되돌립니다.

오답 방지

current > target 가지치기는 모든 수가 양수라는 전제가 있을 때만 안전합니다.

열과 두 대각선 충돌을 상태에 저장하면 보드 전체를 다시 훑지 않아도 됩니다.

정렬 후 같은 값의 사용 순서를 제한해야 같은 결과를 반복 생성하지 않습니다.

성능을 올리려다 정답 후보를 자르면 작은 반례에서 먼저 틀립니다.

depth, state, prune reason을 함께 출력하면 조건 누락 위치를 빨리 찾습니다.

prune cue

가지치기는 빠르게 만드는 코드가 아니라 정답 가능성이 없는 분기만 버린다는 증명이 붙은 조건입니다.