학습 문서 / 정렬 쌍 배제(APE)
Extreme
정렬 쌍 배제(APE)
APE(Aligned Pair Exclusion)는 두 개의 파란 기준 칸을 고른 뒤, 두 칸의 후보를 가능한 모든 방식으로 짝지어 모순이 생기는 조합을 하나씩 제외하는 기법입니다.
기준 칸 A의 한 후보가 기준 칸 B의 모든 후보와 함께 성립할 수 없다면, 그 후보는 A에서 지울 수 있습니다.
1. APE가 이용하는 ALS 성질
ALS(Almost Locked Set, 거의 잠긴 집합)는 같은 행·열·박스 안의 N개 칸에 후보 합집합이 정확히 N+1개 숫자인 집합입니다.
전체에서 숫자 하나가 빠지면 N칸 N숫자의 잠긴 집합이 됩니다. 서로 다른 숫자 두 개가 동시에 빠지면 N칸을 N−1개 숫자로 채워야 하므로 불가능합니다. APE는 이 두 번째 사실로 기준 칸의 조합을 배제합니다.
2. ALS가 조합을 배제하는 조건
A=p, B=q이고 p ≠ q라고 가정합니다. 노란 ALS가 다음을 모두 만족하면 이 조합은 불가능합니다.
p와q가 모두 ALS 후보 합집합에 있다.- A가 ALS 안의 모든
p후보 위치를 본다. - B가 ALS 안의 모든
q후보 위치를 본다.
A=p는 ALS 안의 모든 p를 없애고, B=q는 모든 q를 없앱니다. ALS가 서로 다른 숫자 두 개를 잃어 N칸을 채울 수 없으므로 (p, q)는 성립하지 않습니다. 다른 숫자만 가진 ALS 칸은 두 기준 칸 모두에게 보일 필요가 없고, p와 q가 RCC일 필요도 없습니다.
3. Type 1: 두 기준 칸이 서로 보이는 경우
Type 1에서는 두 파란 칸이 같은 행·열·박스를 공유합니다.
(x, x)는 같은 집에 x가 두 번 놓이므로 직접 충돌합니다.- 서로 다른
(p, q)는 A가 ALS의 모든p, B가 모든q를 볼 때 배제됩니다.
따라서 같은 숫자 충돌도 Type 1 증명의 일부입니다.
4. Type 2: 두 기준 칸이 서로 보이지 않는 경우
Type 2에서는 두 파란 칸이 같은 집을 공유하지 않습니다. 두 칸에 같은 숫자가 동시에 들어갈 수 있으므로 (x, x)는 가능한 조합으로 남겨야 합니다.
두 칸 모두 후보 x를 갖는다면 다른 조합이 모두 막혀도 x를 지울 수 없습니다. Type 2에서 배제되는 각 조합은 서로 다른 두 숫자와 실제 ALS 모순을 가져야 합니다.
5. 조합 배제에서 삭제까지
A의 후보가 1, 4, B가 1, 6, 8이라면 A=4를 B의 모든 후보와 검사합니다.
| A | B | 모순 |
|---|---|---|
| 4 | 1 | ALS P가 4와 1을 동시에 잃음 |
| 4 | 6 | ALS Q가 4와 6을 동시에 잃음 |
| 4 | 8 | ALS R이 4와 8을 동시에 잃음 |
B의 어떤 후보도 A=4와 공존할 수 없으므로 A에서 4를 지울 수 있습니다. 하나의 ALS가 여러 조합을 막아도 되고, 서로 다른 ALS가 각각 막아도 됩니다. 중요한 것은 빠진 조합이 없어야 한다는 점입니다. 반대 방향으로 B의 각 후보도 같은 방식으로 검사합니다.
6. 힌트 색상 읽기
- 파란 칸: 두 기준 칸.
- 초록 후보: 기준 칸에서 서로 짝지어 보는 후보.
- 노란 칸: 모순에 실제로 쓰인 ALS.
- 노란 후보: 가정 때문에 ALS에서 동시에 사라지는 두 숫자.
- 빨간 후보: 상대 칸의 모든 선택과 실패하여 지울 수 있는 후보.
7. 자주 하는 실수
- 한 조합만 막아서는 안 되며 상대 칸의 모든 후보를 막아야 합니다.
- 각 기준 칸은 ALS 안에서 자신이 가정한 숫자의 모든 후보 위치를 봐야 합니다. 관련 없는 ALS 칸은 보이지 않아도 됩니다.
- ALS는 한 집 안의 N칸 N+1숫자여야 합니다.
- 같은 숫자의 직접 충돌은 Type 1에만 적용됩니다. Type 2에서는 허용됩니다.
- 후보가 완전하지 않으면 거짓으로 “모든 조합 실패”가 될 수 있으므로 APE에는 완전한 후보가 필요합니다.
- APE는 쌍, 윙, ALS-XZ와 같은 삭제를 만들 수 있습니다. 여러 설명이 남아도 기본 선택은 더 쉬운 기법입니다.
한 문장으로 기억하세요. 한 후보를 고정하고 다른 칸의 모든 선택을 끝까지 검사해, 어느 길도 가능하지 않을 때만 지웁니다.