스도쿠/공략법/유일성 논법
덤프버전 :
분류
상위 문서: 스도쿠/공략법 1. 개요[편집]
Uniqueness
유일성 논법은 잘 만들어진 스도쿠에 정답은 두 개가 존재할 수 없다는 가정을 적극 이용한 고난도 풀이법이다.
먼저 다음의 스도쿠를 보자.
이 스도쿠를 하나 찾기와 제거하기만으로 열심히 풀어보면 다음과 같이 4칸이 남는다.
남아 있는 4칸의 후보 숫자는 모두 4, 8이다. 즉, 다음의 두 가지 정답이 가능하다는 이야기.
유일성 논법은 주어진 스도쿠의 정답이 하나라는 사실이 알려져 있을 때,[1] 유일성에 위배될만할 후보 숫자를 지우는 논법이다.
1.1. 유일한 직사각형[편집]
Unique Rectangle, Gordonian Logic
Gordonian이란 단어는 이 방법을 처음 고안한 사람의 이름에서 따왔다.
이름대로 두 후보 숫자를 공유하는 두 상자[2]에 걸쳐 있고 직사각형을 이루는 네 개의 칸을 이용한다. 아래는 모두 이 조건을 만족하는 것을 기본 전제로 한다.
네 개의 칸 중 후보 숫자를 두 개만 가지는 칸을 바닥 칸(Floor Square)이라고 한다.
네 개의 칸 중 후보 숫자를 세 개 이상 가지는 칸을 지붕 칸(Roof Square)이라고 한다.
1.1.1. 1 유형[편집]
네 칸 중 세 칸의 칸은 공통된 두 후보숫자만 가지며 나머지 한 칸이 추가적인 후보 숫자를 더 가질 때 그 후보 숫자를 선택할 수 있다.
즉, 세 개의 바닥 칸과 하나의 지붕 칸이 존재할 때, 지붕 칸은 바닥 칸에 포함된 후보 숫자를 제거할 수 있다.
다음의 예제를 보자. 정답은 유일하다.
[ 정답 보기 ]
하나 찾기와 제거하기를 반복하면 다음과 같이 26개의 칸이 남는다. 또한, 설명을 위해 모든 칸에 후보 숫자를 적었다.
노란색과 초록색으로 표기된 네 개의 칸을 보자. 네 칸은 후보 숫자 3, 6을 공유하고 있으며, 초록색 칸에 한해 후보 숫자 2를 추가로 가지고 있다. 만약 초록색 칸에서 후보 숫자 2를 지워버린다면, 3과 6으로 이루어진 직사각형이 완성된다. 즉, 나머지 77칸에 따라, 이 스도쿠의 정답의 개수는 0일 수도 있으며, 짝수일 수도 있다.
처음에 정답은 유일하다고 했으므로, 초록색 칸에서 2는 올바른 후보 숫자이며, 나머지 3과 6을 지워야 한다.
예시와 같이 추가된 수가 하나가 아닌, 여러 개여도 이 방법을 사용할 수 있다.
얼핏 보기엔 엉터리같은 추론이지만 신기하게도 정답이 한개인 스도쿠의 후반부에서는 잘 먹히는 방법이다. 물론 문제 제작자의 미숙으로 정말 정답이 두 개가 나오는 스도쿠 같은 경우는 이 방법이 먹히지 않는다는 것에 주의하자.
1.1.2. 2 유형[편집]
두 개의 바닥 칸과 두 개의 지붕 칸을 가지며 두 지붕 칸이 공통된 하나의 후보숫자만을 추가로 더 가질 때 사용할 수 있다.
즉, 바닥 칸의 후보 숫자 모두가 X, Y이고 지붕 칸의 후보 숫자 모두가 X, Y, Z인 경우이다.
- 2A 유형
2. 한 상자는 두 개의 바닥 칸을, 다른 상자는 두 개의 지붕 칸을 가질 때 사용할 수 있으며
지붕 칸을 모두 포함하는 유닛에서 추가된 하나의 공통된 후보 숫자(Z)를 제거하게 된다.
- 2B 유형
2. 각 상자는 하나의 바닥 칸과 지붕 칸을을 가지고
3. 지붕 칸을 모두 포함하는 유닛이 존재할때[3] 사용할 수 있으며
지붕 칸을 모두 포함하는 유닛에서 추가된 하나의 공통된 후보 숫자(Z)를 제거하게 된다.
지붕 칸을 모두 포함하는 유닛이 행이나 열 중 하나로 고정된다는 사실을 제외하고는 2A와 동일하다.
- 2C 유형
2. 각 상자는 하나의 바닥 칸과 지붕 칸을 가지고
3. 지붕 칸을 모두 포함하는 유닛이 존재하지 않을 때[4] 사용할 수 있으며
지붕 칸이 동시에 바라보는 칸에서 추가된 하나의 공통된 후보 숫자(Z)를 제거하게 된다.
원리와 적용 범위 모두 2A, 2B와 동일하다.
1.1.3. 3 유형[편집]
두 개의 바닥 칸과 두 개의 지붕 칸을 가지며 두 지붕 칸이 다른 하나의 후보숫자만을 추가로 더 가질 때 사용할 수 있다.
즉, 바닥 칸의 후보 숫자 모두가 X, Y이고 지붕 칸의 후보 숫자가 X, Y, Z 또는 W, X, Y인 경우이다.
- 3A 유형
2. 각 상자는 하나의 바닥 칸과 지붕 칸을 가지고 지붕 칸을 모두 포함하는 유닛이 존재할 때 사용할 수 있으며
지붕 칸을 모두 포함하는 유닛에 후보 숫자가 W, Z만인 칸이 존재하면 일종의 네이키드 페어로 작용할 수 있다.
- 3B 유형
2. 한 상자는 두 개의 바닥 칸을, 다른 상자는 두 개의 지붕 칸을 가질 때 사용할 수 있으며
지붕 칸을 모두 포함하는 유닛에 후보 숫자가 W, Z만인 칸이 존재하면 일종의 네이키드 페어로 작용할 수 있다.
1.1.4. 4 유형[편집]
4유형은 다른 유일성 논법에 비해 찾기도 어렵고 외울 것도 많지만, 유일성 논법 중 가장 자주 등장한다.
유일성 논법 4유형은 직사각형 내 후보 숫자 간의 강한 링크를 이용한다. 강한 링크를 2개 또는 1개 찾아서 후보 숫자를 지울 수 있으며, 6가지 패턴이 있다. 각각의 패턴에서 어떤 숫자가 지워지는지 정확히 외워야 한다.
1.1.4.1. 4A 유형[편집]
위와 같이 4개의 칸에 후보 숫자가 적혀 있다. 이때 x와 y는 1, 2가 아닌 후보 숫자이며, 하나 이상일 수도 있고, 서로 같을 수도 있다.
셀 A2와 셀 C2의 후보 숫자 1이 강한 링크를 이룬다고 하자. 셀 C8이 2일 경우, 셀 A8은 2가 아니므로 1이어야 한다. 또한, 셀 A2가 1이 아니므로, 셀 A2는 2이며, 강한 링크에 의해 셀 C2는 1이다. 즉, 고립된 영역이 형성된다.
따라서 고립된 영역을 없애기 위해, 셀 C8에서 후보 숫자 2를 제거해야 한다.
마찬가지로, 아래와 같은 형태에서도 셀 A2와 셀 A8의 후보 숫자 1이 강한 링크를 이룰 경우, 셀 C8에서 후보 숫자 2를 제거할 수 있다.
1.1.4.2. 4B 유형[편집]
4A의 특수한 케이스. 아래와 같은 경우에서 셀 C2와 셀 C8의 후보 숫자 1이 강한 링크를 이룰 경우, 후보 숫자 1에 대해 X-윙이 성립하여 2열과 8열에서도 자동으로 강한 링크를 이룬다. 4A 패턴을 두 번 적용하면, 셀 C2와 셀 C8에서 후보 숫자 2를 제거할 수 있다.
1.1.4.3. 4C 유형[편집]
이 패턴은 다른 패턴과 다르게 강한 링크 하나만 가지고 후보 숫자를 제거할 수 있다.
셀 A2와 셀 C2의 후보 숫자 1이 강한 링크를 이룬다고 하자. 셀 A8이 1일 경우, 셀 A2와 C8은 1이 될 수 없으므로 자동적으로 2가 된다. 셀 A2가 1이 아니므로, 강한 링크에 의해 셀 C2가 1이 된다. 즉, 고립된 영역이 형성된다.
따라서 셀 A8에서 후보 숫자 1을 제거한다.
1.1.4.4. 4D 유형[편집]
여기부터는 잠재적인 고립된 패턴이 잘 드러나지 않아, 기법 적용에 어려움이 있을 수 있다.
위와 같은 경우에서 후보 숫자 1이 셀 A8과 셀 C8, 그리고 셀 C2와 셀 C8에서 각각 강한 링크를 이룬다고 하자. 셀 C8이 2일 경우, 1이 아니므로 강한 링크에 의해 셀 A8과 C2는 자동적으로 1이 된다. 그러면 셀 A2는 1이 아니므로 2가 된다. 즉, 고립된 영역이 형성된다.
따라서 셀 C8에서 후보 숫자 2를 제거할 수 있다.
1.1.4.5. 4E 유형[편집]
위와 같은 경우에서 셀 A2와 셀 A8의 후보 숫자 1이 강한 링크를 이루고, 셀 A8과 셀 C8의 후보 숫자 2가 강한 링크를 이룬다고 하자. 셀 C2가 1일 경우, 셀 A2가 1이 아니므로 셀 A2는 2이고, 강한 링크에 의해 셀 A8은 1이다. 셀 A8이 2가 아니므로, 강한 링크에 의해 셀 C8은 2이다. 즉, 고립된 영역이 형성된다.
따라서 셀 C2에서 후보 숫자 1을 제거할 수 있다.
1.1.4.6. 4F 유형[편집]
위와 같은 경우에서 셀 A8과 셀 C8의 후보 숫자 1이 강한 링크를 이루고, 셀 C2와 셀 C8의 후보 숫자 2가 강한 링크를 이룬다고 하자. 셀 A8이 2일 경우, 셀 A2는 1이다. 셀 A8이 1이 아니므로, 강한 링크에 의해 셀 C8은 1이다. 셀 C8이 2가 아니므로, 강한 링크에 의해 셀 C2는 2이다. 즉, 고립된 영역이 형성된다.
같은 방법으로, 셀 C2가 1일 경우에도 고립된 영역이 형성된다. 따라서 셀 A8에서 후보 숫자 2, 셀 C2에서 후보 숫자 1을 제거할 수 있다.
[ 정답 보기 ]
이 퍼즐을 기초 기법과 상호작용, 짝맞추기만으로 풀어보면 다음과 같이 43개의 빈칸이 남는다. 여기서 규칙 4가 적용될만한 곳을 네 군데 찾아보자.
먼저 셀 D1, D3, I1, I3으로 이루어진 직사각형 (편의상 직사각형 DI13으로 부른다.)을 보자. 네 개의 셀은 모두 후보 숫자 1, 4를 포함하고 있으며, 그 중에서 셀 D1과 셀 D3은 1, 4 이외에 다른 후보 숫자가 없다. 또한, 3열을 볼 때, 셀 D3과 셀 I3의 후보 숫자 1은 강한 링크를 갖는다.
따라서 유일성 논법 4A유형에 의해, 셀 I1에서 후보 숫자 4를 제거한다.
다음으로, 직사각형 FG79를 보자. 네 개의 칸은 모두 후보 숫자 5, 6을 포함하고 있으며, 그 중에서 셀 F9과 셀 G7은 5, 6 이외에 다른 후보 숫자가 없다. 또한, 6행과 9열에서 셀 F7과 셀 F9의 후보 숫자 5, 그리고 셀 F9과 셀 G9의 후보 숫자 5는 각각 강한 링크를 갖는다.
따라서 유일성 논법 4C유형에 의해, 셀 G9과 셀 F7에서 후보 숫자 5를 제거하며, 셀 F9는 5로 확정된다.
이번에는 직사각형 GH25를 보자. 네 개의 칸은 모두 후보 숫자 5, 9를 포함하고 있으며, 셀 G2와 셀 H5는 5, 9 이외에 다른 후보 숫자가 없다. 또한, 8행을 보면 셀 H2와 셀 H5의 후보 숫자 5가 강한 링크를 이루고 있으며, 7행과 5열을 보면 셀 G2와 셀 G5의 후보 숫자 9, 그리고 셀 G5와 셀 H5의 후보 숫자 9도 각각 강한 링크를 가진다.
따라서 유일성 논법 4C유형에 의해 셀 G5에서 후보 숫자 5, 셀 H2에서 후보 숫자 9를 제거한다.
마지막으로 직사각형 AD78을 보자. 네 개의 칸은 모두 후보 숫자 1, 6을 포함하고 있으며, 셀 A8은 1, 6 이외의 다른 후보 숫자가 없다. 또한, 직사각형 AD78에서 후보 숫자 1이 X-윙을 이루고 있다.
따라서 유일성 논법 4D유형에 의해, 셀 D7에서 후보 숫자 6을 제거한다.
이후에는 XY-윙과 XY-체인을 이용하여 문제를 해결할 수 있다.
1.1.5. 5 유형[편집]
유일성 논법의 정수. 앞의 1 ~ 4유형은 네 개의 칸이 모두 비어 있고 네 칸 모두 특정 후보 숫자 2개를 포함하는 겅우만 다루었다. 그러나 심플 컬러링, XY-윙 등의 기법으로 후보 숫자 하나가 지워졌을 때에도 거의 똑같은 방법으로 유일성 논법을 사용할 수 있다. 각각의 패턴은 1 ~ 4유형과 대응된다.
1.1.6. 확장된 유일한 직사각형[편집]
Extended Unique Rectangles
1.1.7. 숨겨진 유일한 직사각형[편집]
Hidden Unique Rectangles
1.1.8. 피할 수 있는 유일한 직사각형[편집]
Avoidable Rectangles
1.2. 버그[편집]
BUG(Bi-Value Universal Grave)
스도쿠에 남은 모든 칸들이 후보 숫자를 2개씩만 가지면(버그가 발생하면) 해답이 없거나 2개임을 이용한다.
스도쿠에 후보 숫자를 적절히 기입하였다.
여기서 셀 F3에 집중하여 보자.
후보 숫자 2나 5이 들어가지 않는다고 가정하는 것은 문제되지 않는다. 제거하기(Hidden Single)에 의하여 각각 셀 E3, D3의 후보 숫자를 하나로 정할 수 있을 것이고 이것은 연쇄적으로 답을 찾아나가게 한다.
그러나 후보 숫자 8이 셀 F3에 들어가지 않는다고 가정하면 스도쿠에 남은 모든 칸들이 후보 숫자를 2개씩만 가지게 된다. 이는 아래 증명에 의하여 스도쿠가 해답이 없거나 2개임을 의미하므로 셀 F3에는 8이 들어가야만 한다.
위와 같이 특정 하나의 칸을 제외한 모든 칸에 후보 숫자가 존재할 때를 BUG+1이라 한다.
그러면 특정 두 개의 칸을 제외한 모든 칸에 후보 숫자가 존재할 때를 BUG+2라 생각하고 같은 논리를 적용시킬 수 있을 것이다.
* 특정 두 칸의 버그에 사용되는 후보 숫자가 같을 때:
* 특정 두 칸이 버그에 사용되는 후보 숫자가 다를 때: 거의 잠긴 세트의 발상을 이용한다. 만약 특정 두 칸이 한 행위에 있고 두 후보 숫자를 가지는 거의 잠긴 세트가 있다고 가정하면 이를 통해 드러난 두 짝 기법을 쓸 수 있을 것이다. 일반적인 담론에 대해서는 상위 문서의 세트 단락을 확인하자.
역시 특정 n 개의 칸을 제외한 모든 칸에 후보 숫자가 존재할 때를 BUG+n라 생각할 수 있다. 설혹 이 경우를 만난다 하더라도 같은 논리를 적용하면 쉬이 해결할 수 있을 것이다.
1.2.1. 증명[편집]
이 문서의 내용 중 전체 또는 일부는 2023-12-04 16:08:33에 나무위키 스도쿠/공략법/유일성 논법 문서에서 가져왔습니다.