스도쿠/공략법/킬러 스도쿠

상위 문서: 스도쿠/공략법

1. 개요2. 도입

2.1. 용어

3. 초급

3.1. 조합3.2. 45의 법칙

4. 중급

4.1. 조합의 확장4.2. 45의 법칙의 확장

4.2.1. 유닛이 2개 이상인 경우4.2.2. 유닛에 포함되지 않은 칸이 2개 이상인 경우

5. 고급

5.1. 거의 잠긴 집합

5.1.1. 우리 분할5.1.2. 이중값 공격

1. 개요

킬러 스도쿠(Killer Sudoku)의 공략법에 대해 서술하는 문서

킬러 스도쿠는 스도쿠의 확장이기에 스도쿠/공략법의 기법들을 모두 사용할 수 있다. 이 문서는 킬러 스도쿠에서만 사용할 수 있는 기법만 서술한다.

2. 도입

2.1. 용어

스도쿠/공략법에 서술되어 있는 용어를 그대로 사용하며 아래의 용어를 추가로 사용한다.

우리(Cage): 칸들에 들어갈 수 있는 숫자들의 합이 주어지는 칸들의 모임. 일반적으로 칸들의 숫자는 중복되지 않는다.[1]
우리 크기(Cage Size): 우리에 포함된 칸들의 개수
우리 값(Cage Value): 우리에 포함된 칸에 들어갈 수 있는 숫자들의 합

3. 초급

킬러 스도쿠 풀이의 기초가 된다.
아래 모든 기법들은 이 두 개의 기법들로부터 파생된다.

3.1. 조합

Combinations, Magic Number
가쿠로의 족보와 같다.

특수한 경우에, 우리 크기와 값에 따라 칸에 들어갈 숫자의 특정 조합이 정해진다. 예를 들어, 우리 크기가 2이며 우리 값이 3인 경우 우리의 칸은 1과 2만 포함할 수 있다. 아래는 유일한 조합 목록이다.

우리 크기	우리 값	조합
1	n	n
2	3	1, 2
2	4	1, 3
2	16	7, 9
2	17	8, 9
3	6	1, 2, 3
3	7	1, 2, 4
3	23	6, 8, 9
3	24	7, 8, 9
4	10	1, 2, 3, 4
4	11	1, 2, 3, 5
4	29	5, 7, 8, 9
4	30	6, 7, 8, 9
5	15	1, 2, 3, 4, 5
5	16	1, 2, 3, 4, 6
5	34	4, 6, 7, 8, 9
5	35	5, 6, 7, 8, 9
6	21	1, 2, 3, 4, 5, 6
6	22	1, 2, 3, 4, 5, 7
6	38	3, 5, 6, 7, 8, 9
6	39	4, 5, 6, 7, 8, 9
7	28	1, 2, 3, 4, 5, 6, 7
7	29	1, 2, 3, 4, 5, 6, 8
7	41	2, 4, 5, 6, 7, 8, 9
7	42	3, 4, 5, 6, 7, 8, 9
8	n	(45-n)을 제외한 모든 수
9	45	1, 2, 3, 4, 5, 6, 7, 8, 9

킬러 스도쿠를 자주 풀다보면 이에 익숙해지지만 처음에 많은 조합들을 모두 다 외우는 것은 힘들 수 있다. 따라서 아래에 모든 가능한 조합들을 접어 놓는다.

[조합]

||<tablebordercolor=#000000><table bgcolor=#FFFFFF,#444444><table width=500px><width=50px><:>우리 크기||<width=50px><:>우리 값||<width=200px><:>조합||<width=200px><:>가능한 후보 숫자||

1	1	1	1(유일)
1	2	2	2(유일)
1	3	3	3(유일)
1	4	4	4(유일)
1	5	5	5(유일)
1	6	6	6(유일)
1	7	7	7(유일)
1	8	8	8(유일)
1	9	9	9(유일)
2	3	1, 2	1, 2(유일)
2	4	1, 3	1, 3(유일)
2	5	1, 4	1, 2, 3, 4
2	5	2, 3	1, 2, 3, 4
2	6	1, 5	1, 2, 4, 5
2	6	2, 4	1, 2, 4, 5
2	7	1, 6	1, 2, 3, 4, 5, 6
		2, 5
		3, 4
2	8	1, 7	1, 2, 3, 5, 6, 7
		2, 6
		3, 5
2	9	1, 8	1, 2, 3, 4, 5, 6, 7, 8
		2, 7
		3, 6
		4, 5
2	10	1, 9	1, 2, 3, 4, 6, 7, 8, 9
		2, 8
		3, 7
		4, 6
2	11	2, 9	2, 3, 4, 5, 6, 7, 8 9
		3, 8
		4, 7
		5, 6
2	12	3, 9	3, 4, 5, 7, 8, 9
		4, 8
		5, 7
2	13	4, 9	4, 5, 6, 7, 8, 9
		5, 8
		6, 7
2	14	5, 9	5, 6, 8, 9
2	14	6, 8	5, 6, 8, 9
2	15	6, 9	6, 7, 8, 9
2	15	7, 8	6, 7, 8, 9
2	16	7, 9	7, 9(유일)
2	17	8, 9	8, 9(유일)
3	6	1, 2, 3	1, 2, 3(유일)
3	7	1, 2, 4	1, 2, 4(유일)
3	8	1, 2, 5	1, 2, 3, 4, 5
3	8	1, 3, 4	1, 2, 3, 4, 5
3	9	1, 2, 6	1, 2, 3, 4, 5, 6
		1, 3, 5
		2, 3, 4
3	10	1, 2, 7	1, 2, 3, 4, 5, 6, 7
		1, 3, 6
		1, 4, 5
		2, 3, 5
3	11	1, 2, 8	1, 2, 3, 4, 5, 6, 7, 8
		1, 3, 7
		1, 4, 6
		2, 3, 6
		2, 4, 5
3	12	1, 2, 9	1, 2, 3, 4, 5, 6, 7, 8, 9
		1, 3, 8
		1, 4, 7
		1, 5, 6
		2, 3, 7
		2, 4, 6
		3, 4, 5
3	13	1, 3, 9	1, 2, 3, 4, 5, 6, 7, 8, 9
		1, 4, 8
		1, 5, 7
		2, 3, 8
		2, 4, 7
		2, 5, 6
		3, 4, 6
3	14	1, 4, 9	1, 2, 3, 4, 5, 6, 7, 8, 9
		1, 5, 8
		1, 6, 7
		2, 3, 9
		2, 4, 8
		2, 5, 7
		3, 4, 7
		3, 5, 6
3	15	1, 5, 9	1, 2, 3, 4, 5, 6, 7, 8, 9
		1, 6, 8
		2, 4, 9
		2, 5, 8
		2, 6, 7
		3, 4, 8
		3, 5, 7
		4, 5, 6
3	16	1, 6, 9	1, 2, 3, 4, 5, 6, 7, 8, 9
		1, 7, 8
		2, 5, 9
		2, 6, 8
		3, 4, 9
		3, 5, 8
		3, 6, 7
		4, 5, 7
3	17	1, 7, 9	1, 2, 3, 4, 5, 6, 7, 8, 9
		2, 6, 9
		2, 7, 8
		3, 5, 9
		3, 6, 8
		4, 5, 8
		4, 6, 7
3	18	1, 8, 9	1, 2, 3, 4, 5, 6, 7, 8, 9
		2, 7, 9
		3, 6, 9
		3, 7, 8
		4, 5, 9
		4, 6, 8
		5, 6, 7
3	19	2, 8, 9	2, 3, 4, 5, 6, 7, 8, 9
		3, 7, 9
		4, 6, 9
		4, 7, 8
		5, 6, 8
3	20	3, 8, 9	3, 4, 5, 6, 7, 8, 9
		4, 7, 9
		5, 6, 9
		5, 7, 8
3	21	4, 8, 9	4, 5, 6, 7, 8, 9
		5, 7, 9
		6, 7, 8
3	22	5, 8, 9	5, 6, 7, 8, 9
3	22	6, 7, 9	5, 6, 7, 8, 9
3	23	6, 8, 9	6, 8, 9(유일)
3	24	7, 8, 9	7, 8, 9(유일)
4	10	1, 2, 3, 4	1, 2, 3, 4(유일)
4	11	1, 2, 3, 5	1, 2, 3, 5(유일)

8	36	1, 2, 3, 4, 5, 6, 7, 8	1, 2, 3, 4, 5, 6, 7, 8(유일)
8	37	1, 2, 3, 4, 5, 6, 7, 9	1, 2, 3, 4, 5, 6, 7, 9(유일)
8	38	1, 2, 3, 4, 5, 6, 8, 9	1, 2, 3, 4, 5, 6, 8, 9(유일)
8	39	1, 2, 3, 4, 5, 7, 8, 9	1, 2, 3, 4, 5, 7, 8, 9(유일)
8	40	1, 2, 3, 4, 6, 7, 8, 9	1, 2, 3, 4, 6, 7, 8, 9(유일)
8	41	1, 2, 3, 5, 6, 7, 8, 9	1, 2, 3, 5, 6, 7, 8, 9(유일)
8	42	1, 2, 4, 5, 6, 7, 8, 9	1, 2, 4, 5, 6, 7, 8, 9(유일)
8	43	1, 3, 4, 5, 6, 7, 8, 9	1, 3, 4, 5, 6, 7, 8, 9(유일)
8	44	2, 3, 4, 5, 6, 7, 8, 9	2, 3, 4, 5, 6, 7, 8, 9(유일)
9	45	1, 2, 3, 4, 5, 6, 7, 8, 9	1, 2, 3, 4, 5, 6, 7, 8, 9(유일)

3.2. 45의 법칙

The Rule of 45
스도쿠의 규칙상 모든 유닛에는 1부터 9까지의 숫자가 중복없이 모두 들어가야하며 이는 유닛에 들어가는 숫자의 합은 45이어야 함을 의미한다.

따라서 만약 한 유닛을 거의 덮고 있지만 한 개의 우리만 나와있거나(Outie), 한 개의 우리만 들어가있는(Innie) 경우를 찾을 수 있다면 이를 이용할 수 있다.

먼저 9행에 집중하여 보자.
9행의 세 개의 우리는 전부 9행에 속하며 한 개의 우리의 한 개의 칸이 9행 안으로 들어와 있다.
이런 경우를 Innie라 하며 안으로 들어온 칸에 들어갈 숫자를 [math(45-15-18-11=1)]로 확정할 수 있다.

다음으로 7번 상자에 집중하여 보자.
7번 상자의 세 개의 우리는 전부 7번 상자에 속하며 한 개의 우리의 한 개의 칸만 7번 상자 바깥으로 나와 있다.
이런 경우를 Outie라고 하며 바깥으로 나간 칸에 들어갈 숫자를 [math(18-(45-15-15-4)=18-11=7)]로 확정할 수 있다.

나머지 표시된 숫자들은 전부 이 45의 법칙에 의하여 구할 수 있는 숫자들이다.[2] 한 번 시도해보자.

4. 중급

4.1. 조합의 확장

4.2. 45의 법칙의 확장

4.2.1. 유닛이 2개 이상인 경우

위의 45의 법칙 예제 그대로이다.

이번에는 2, 3번 두 상자에 동시에 집중해 보자. 다른 우리들은 모두 이 두 상자에 속하여 있지만 하나의 우리의 하나의 칸만이 들어가있다(나와 있다).

위와 동일한 방법으로 계산하되, 이번에는 유닛이 2개이므로 그 합은 [math(45times2=90)]이다. 따라서
Innie를 보고 [math(90-14-11-8-8-16-5-10-15=3)]으로 계산하든가
Outie를 보고 [math(5-(90-14-11-8-8-16-5-10-15)=5-3=2)]로 계산하든 결과는 같다.

여기에서는 2개의 상자에 대하여 계산했지만 2개의 열이나 행 따위에도 모두 적용할 수 있다.

또한, 2개의 유닛이 아닌 3개 이상의 유닛에서도 마찬가지의 방법을 적용할 수 있다.

4.2.2. 유닛에 포함되지 않은 칸이 2개 이상인 경우

똑같은 그림이다. 킬러 스도쿠가 익숙하지 않다면 윗 문단 조합의 모든 조합 목록을 펼쳐서 옆에 띄워 놓고 읽자.

이번에는 2번, 3번 상자에 각각 집중해 보자.

먼저 2번 상자에 집중하면 3개의 우리가 모두 2번 상자에 포함되어 있고 초록색으로 칠한 2개의 칸이 유닛 안으로 들어와 있다.(Inne)
이 경우 초록색 칸에 들어갈 숫자의 합은 [math(45-14-11-16=4)]이 될 것이며 일종의 거짓우리(Pseudo-Cage)를 형성한다.
즉, 초록색 칸은 우리의 크기가 2이고 값이 4인 우리로써 기능하며 이 두 셀 A6, B6의 후보 숫자는 1과 3뿐일 것이다.

마찬가지의 방법으로 3번 상자에 집중하면 파란색 칸은 우리의 크기가 2이고 값이 [math(45-5-10-15-3=12)]인 거짓우리를 형성한다. 그러면 조합 목록에 따라 후보 숫자 1, 2를 파란색 칸에서 제거할 수 있을 것이다.

이 이후는 같은 방법을 사용할 수 있음을 알리려는 것이지 적용할 수 없어도 괜찮다.

1행을 보자. 우리의 크기가 5, 8인 우리를 제외한 나머지 5개의 칸을 크기가 5이고 값이 32인 거짓우리로 여길 수 있다.
조합 목록에 따라 후보 숫자 1을 이 5개의 칸에서 제거할 수 있다.

또한, 이 예제에서 지금 상태로는 보이지 않으나 단순히 가능한 후보 숫자를 보는 것이 아닌 가능한 조합을 모두 고려한 후 되지 않는 조합을 제거하는 방법을 통해 후보 숫자를 제거할 수도 있다.

5. 고급

5.1. 거의 잠긴 집합

Almost Locked Set
거의 잠긴 집합에 대한 이해가 어느 정도 필요하다. 이는 스도쿠/공략법의 고급 문단에 서술되어 있으며 관련 내용에 대한 이해가 필수는 아니지만 이해를 권장한다.

한 유닛의 n개의 칸에 n개의 후보 숫자가 들어 있는 경우 그 n개의 칸을 잠긴 집합(Locked Set, LS)이라 한다.
한 유닛의 n개의 칸에 n+1개의 후보 숫자가 들어 있는 경우 그 n개의 칸을 거의 잠긴 집합(Almost Locked Set, ALS)라 한다.

5.1.1. 우리 분할

Cage Split
잠긴 집합을 이용하여 우리를 분할한다.

5.1.2. 이중값 공격

Bi-Value attack
문서 제목은 ALS 중 1개의 칸에 2개의 후보 숫자가 들어 있는 이중값(Bi-Value)에 대해서만 적용할 수 있는 것처럼 보이지만 ALS에 대한 이해가 충분하다면 그렇지 않다는 것을 알 것이다.

ALS의 여러 기법들 중 부분집합 제거와 비슷 논리로 ALS을 포함한 유닛의 다른 칸에 그 후보 숫자가 둘 이상 있으면 모순임을 이용한다.

[1] 만약 우리에 포함된 칸의 숫자가 중복됨을 허용하는 킬러 스도쿠의 경우 아래 기법들을 적절히 변형하여 사용하여야 한다.[2] 2개 이상의 유닛을 사용하거나 2개 이상의 칸이 유닛에 포함되지 않은 경우는 아래 중급 문단에 서술한다.

스도쿠/공략법/킬러 스도쿠

1. 개요

2. 도입

2.1. 용어

3. 초급

3.1. 조합

3.2. 45의 법칙

4. 중급

4.1. 조합의 확장

4.2. 45의 법칙의 확장

4.2.1. 유닛이 2개 이상인 경우

4.2.2. 유닛에 포함되지 않은 칸이 2개 이상인 경우

5. 고급

5.1. 거의 잠긴 집합

5.1.1. 우리 분할

5.1.2. 이중값 공격

분류