Sue de Coq

먼저 읽으면 좋은 내용: 후보 표기 · 쌍과 부분집합 · ALS-XZ

Sue de Coq는 원래 Two-Sector Disjoint Subsets라고 불렸습니다. 행 또는 열과 박스의 교차 영역에 양쪽 ALS를 결합하는 기법입니다.

후보가 겹치지 않는 두 ALS가 각각 한 숫자를 교차 영역에 남깁니다. 그 결과 교차 영역을 공유하는 두 잠금 집합이 만들어집니다.

1. 구성 요소

잠금 집합은 같은 하우스의 N개 셀에 후보가 정확히 N종류 있는 집합입니다. 그 N개 숫자가 셀을 모두 채워야 합니다.

ALS(Almost Locked Set)는 같은 하우스의 N개 셀에 N+1종류 후보가 있는 집합입니다. N개 셀을 채우면 ALS 후보 중 정확히 한 숫자가 사용되지 않습니다. 두 후보 셀은 1셀 2후보인 가장 작은 ALS입니다.

교차 영역 C는 선택한 행·열과 박스에 동시에 속한 미완성 셀입니다. 후보 합집합을 V라고 합니다. 전형적인 형태는 2셀 4후보 또는 3셀 5후보입니다.

2. 엄격한 조건

• 파란 셀: 교차 영역 C.
• 노란 셀: C 밖의 행·열 쪽 ALS L.
• 초록 셀: C 밖의 박스 쪽 ALS B.
• 빨간 후보: 제거할 후보.

다음 조건이 모두 필요합니다.

1. C는 최소 2셀입니다.
2. L은 p셀에 정확히 p+1 후보입니다.
3. B는 q셀에 정확히 q+1 후보입니다.
4. L과 B의 후보는 모두 V에 포함됩니다.
5. L과 B는 어떤 후보 숫자도 공유하지 않습니다.
6. |C| + |L| + |B| = |V|입니다.

양쪽 후보의 비중복과 마지막 등식이 핵심 안전 조건입니다. 하나라도 빠지면 교차 영역에 추가 선택지가 남습니다.

3. 증명

노란 ALS는 p+1 후보 중 p개 숫자로 p셀을 채우므로 정확히 한 후보를 사용하지 않습니다. 초록 ALS도 정확히 한 후보를 사용하지 않습니다.

모든 파란 셀은 행·열을 통해 모든 노란 셀을 보고, 박스를 통해 모든 초록 셀을 봅니다. 한쪽 ALS에서 이미 사용한 숫자는 C에서 반복될 수 없습니다. C에 남는 숫자는 다음뿐입니다.

• 노란 ALS가 사용하지 않은 한 숫자.
• 초록 ALS가 사용하지 않은 한 숫자.
• 어느 쪽에도 배정되지 않은 V의 숫자.

개수 등식 때문에 남은 숫자의 수는 정확히 |C|입니다. 따라서 C가 이 숫자를 모두 받아야 합니다.

노란 후보는 노란 ALS에서 쓰이거나, 빠진 숫자라면 C에서 쓰입니다. 어느 경우든 행·열 안에 잠깁니다. 초록 후보도 초록 ALS 또는 C에서 쓰이므로 박스 안에 잠깁니다. 교차 영역 전용 후보는 C에만 들어가므로 두 하우스 모두에서 잠깁니다.

4. 기본 예

파란 2셀의 후보 합집합이 1,2,3,4, 노란 두 후보 셀이 1,2, 초록 두 후보 셀이 3,4라고 합시다.

노란 셀은 1,2 중 하나를 쓰고 다른 하나를 C에 남깁니다. 초록 셀도 3,4 중 하나를 쓰고 다른 하나를 C에 남깁니다. 따라서 1,2는 행·열에, 3,4는 박스에 잠깁니다.

파란 3셀이 1,2,3,4,5이고 양쪽이 1,2와 3,4를 맡으면 5는 C 전용입니다. 5는 행·열과 박스 양쪽에서 잠깁니다.

5. 여러 셀로 된 측면 ALS

측면은 한 개의 두 후보 셀일 필요가 없습니다. 초록 셀 3,4와 4,5는 2셀 3후보 ALS입니다. 두 숫자를 사용하고 남은 한 숫자를 C에 넘깁니다. 개별 셀이 아니라 전체 그룹이 N셀 N+1후보인지 확인해야 합니다.

6. 다른 기법과 구현 범위

ALS-XZ는 RCC로 두 ALS를 연결합니다. APE는 두 기준 셀의 모든 후보 조합을 검사합니다. Sue de Coq는 RCC 체인이나 조합 열거 없이 V를 겹치지 않는 두 측면에 나누고 정확한 개수로 잠금을 증명합니다.

앱은 여러 셀 측면 ALS를 포함한 엄격한 V 내부 형태를 구현합니다. 일부 자료는 이 일반화도 Extended Sue de Coq로 분류합니다. 더 넓은 확장 형태는 V 밖의 측면 후보를 허용하거나 3셀 교차 영역의 일부만 사용할 수 있습니다. 추가 셀과 일반화된 계산식이 필요하므로 여기서는 검출하지 않습니다.

7. 흔한 오판

• 두 측면이 같은 후보를 공유합니다.
• 측면이 정확히 N셀 N+1후보가 아닙니다.
• 측면 후보가 V 밖에 있습니다.
• 색칠된 전체 셀 수가 |V|와 다릅니다.
• 노란 후보를 박스에서, 또는 초록 후보를 잘못된 행·열에서 제거합니다.
• 후보 표기가 완전하지 않습니다.

8. 확인 순서

1. C와 V를 찾습니다.
2. 노란·초록 ALS를 각각 N/N+1로 확인합니다.
3. 양쪽 후보가 겹치지 않는지 확인합니다.
4. |C| + |L| + |B| = |V|를 확인합니다.
5. 노란 후보를 나머지 행·열에서 제거합니다.
6. 초록 후보를 나머지 박스에서 제거합니다.
7. C 전용 후보를 두 하우스 모두에서 확인합니다.