BUG+1: 왜 답이 하나뿐이라는 전제가 필요한가요?

후보가 셋인 칸 하나만 찾으면 될까요?

BUG+1은 답이 하나뿐인 퍼즐에서, 거의 모든 빈칸이 후보 둘을 가진 특수한 상태를 이용합니다. 하지만 「후보가 셋인 칸이 하나 있고 나머지는 둘」이라는 겉모양만으로는 부족합니다. 줄마다 숫자의 등장 횟수도 확인해야 하고, 무엇보다 답이 하나뿐이라는 전제가 필요합니다.

유일성은 행 · 열 · 박스에 1부터 9까지 한 번씩 넣는 규칙과 별개입니다. 그 규칙을 모두 지키는 완성판이 둘 이상일 수도 있습니다. 직접 입력한 판이나 단서를 지운 판에서는 유일성을 먼저 확인하세요.

적용 조건 — 전제부터, 칸 수와 줄별 횟수까지

1. 현재 판이 유일해이고, 이전에 넣은 숫자나 지운 후보도 옳아야 합니다.
2. 빈칸 하나에만 후보가 정확히 셋이고, 나머지 모든 빈칸에는 후보가 정확히 둘이어야 합니다.
3. 후보 셋인 칸에서 숫자 하나를 가상으로 지웠을 때, 남은 각 후보 숫자가 등장하는 모든 행 · 열 · 박스에서 정확히 두 번씩 등장해야 합니다. 이미 채워진 숫자의 후보 등장 횟수는 0입니다.
4. 따라서 지우기 전 그 숫자는 특수 칸이 속한 행 · 열 · 박스 각각에서 세 번 등장합니다. 한 줄의 세 번만 세고 끝내면 안 됩니다.

이렇게 모든 빈칸이 두 후보씩이고 줄별 등장도 두 번씩인 상태를 BUG라고 합니다. 그 상태에 해가 있다면 선택들을 뒤집은 다른 해도 있으므로, 해가 하나만 있을 수 없습니다. 해가 없을 가능성도 있습니다. 유일해 판에서는 그 상태를 그대로 남길 수 없으므로, BUG를 깨는 추가 후보 하나를 특수 칸에 넣습니다.

예제 — r7c6 의 추가 후보는 무엇인가요?

c1c2c3c4c5c6c7c8c9

r1r2r3r4r5r6r7r8r9

68

7

36

89

5

1

39

4

2

9

1

5

2

4

3

7

8

6

28

4

23

7

6

89

39

5

1

4

2

8

69

3

69

5

1

7

5

6

9

4

1

7

2

3

8

1

3

7

58

2

58

4

6

9

3

8

26

56

7

256

1

9

4

7

9

1

3

8

4

6

2

5

26

5

4

1

9

26

8

7

3

★

★ r7c6 의 후보는 2, 5, 6입니다. 다른 빈칸은 모두 후보 둘뿐입니다. 숫자 6의 위치를 세어 보세요.

• 7행: r7c3, r7c4, r7c6 세 칸입니다.
• 6열: r4c6, r7c6, r9c6 세 칸입니다.
• 8번 박스: r7c4, r7c6, r9c6 세 칸입니다.

r7c6 의 6을 빼면 이 세 곳의 6도 두 자리씩 남고, 다른 모든 후보의 줄별 등장 횟수도 0 또는 2입니다. 이 판은 백트래킹으로 해가 하나임을 확인했습니다. 따라서 r7c6=6입니다. 2나 5를 넣으면 유일해라는 전제와 양립할 수 없습니다. 확정한 뒤에는 같은 행 · 열 · 박스의 6 후보를 지우고 기본 풀이로 돌아갑니다.

적용할 수 없는 경우와 흔한 오해

• 해가 몇 개인지 모릅니다. 생성기가 유일성을 보장하거나 별도 검증한 판에서만 이 전제를 쓰세요. 논리 풀이기에 BUG+1을 켜는 동작 자체가 유일성 검사는 아닙니다.
• 후보가 셋인 칸이 둘 이상입니다. 이 글의 BUG+1 조건에 맞지 않습니다.
• 후보 수는 맞지만 줄별 횟수가 다릅니다. BUG가 아니므로 추가 후보를 확정할 수 없습니다.
• 후보를 빠뜨렸습니다. 틀린 메모로 만든 BUG 모양은 근거가 되지 않습니다.
• BUG이면 반드시 해가 정확히 둘이라고 생각합니다. 여기서 필요한 것은 유일해일 수 없다는 사실입니다. 별개로 움직이는 부분이 있으면 해가 더 많을 수 있습니다.

비유일해 반례 — 같은 조건이어도 8을 확정할 수 없습니다

c1c2c3c4c5c6c7c8c9

r1r2r3r4r5r6r7r8r9

8

7

6

9

5

1

3

4

2

9

1

5

2

4

3

78

78

6

2

4

3

7

6

8

9

5

1

4

2

8

6

3

9

5

1

7

5

6

9

4

1

7

2

38

38

1

3

7

8

2

5

4

6

9

3

8

2

5

7

6

1

9

4

7

9

1

3

8

4

6

2

5

6

5

4

1

9

2

78

378

38

★

이 반례는 생성기의 완성판에서 단서를 지우고 논리 풀이로 정리해 찾았습니다. 후보가 셋인 칸은 r9c8 하나이며, 추가 후보처럼 보이는 숫자는 8입니다. 9행에서는 r9c7·r9c8·r9c9, 8열에서는 r2c8·r5c8·r9c8, 9번 박스에서는 r9c7·r9c8·r9c9 에 8이 세 번씩 남습니다. 다른 후보의 등장 횟수도 0 또는 2여서, 유일해를 제외한 BUG+1의 후보 조건은 모두 맞습니다.

하지만 해의 개수 검사 결과는 2개 이상입니다(검사기는 두 개를 찾으면 멈춥니다). 유일성을 확인하지 않고 BUG+1을 켜면 풀이기는 r9c8=8을 제안합니다. 다음 두 완성 방법도 모두 행 · 열 · 박스 규칙을 지키므로 그 확정은 필수가 아닙니다. 아래 일곱 칸 외에는 도식의 숫자를 그대로 둡니다.

빈칸	완성 방법 A	완성 방법 B
r2c7	7	8
r2c8	8	7
r5c8	3	8
r5c9	8	3
r9c7	8	7
r9c8	7	3
r9c9	3	8

r9c8 은 A에서는 7, B에서는 3입니다. 따라서 「r9c8 은 반드시 8」이라는 결론은 틀립니다. 8인 해도 존재하지만, 가능한 해 하나를 골랐다는 것과 모든 해에서 성립하는 확정은 다릅니다. 이 반례는 해가 여러 개라서 생기는 실제 실패이며, 후보를 빠뜨린 가짜 모양이 아닙니다.

연습 문제

c1c2c3c4c5c6c7c8c9

r1r2r3r4r5r6r7r8r9

8

24

39

49

7

6

23

5

1

1

24

39

5

49

8

7

6

23

5

6

7

3

1

2

4

9

8

6

9

5

2

3

1

8

4

7

7

3

1

8

6

4

9

2

5

2

8

4

7

5

9

1

3

6

39

7

2

49

8

5

6

1

34

39

5

6

1

49

7

23

8

234

4

1

8

6

2

3

5

7

9

★

★ r8c9 의 후보는 2, 3, 4입니다. 이 판도 유일해입니다. 어느 후보를 넣어야 하나요? 세 번 등장하는 세 영역을 좌표로 적어 보세요.

답 보기

r8c9=3입니다. 8행의 3은 r8c1, r8c7, r8c9, 9열의 3은 r2c9, r7c9, r8c9, 9번 박스의 3은 r7c9, r8c7, r8c9에 있습니다. r8c9 의 3을 빼면 다른 빈칸을 포함한 모든 후보가 등장하는 영역마다 두 번씩 남습니다. 유일해라는 전제 때문에 그 BUG 상태를 피해야 하므로 추가 후보 3을 넣습니다.

이어서 읽기

선수 지식은 후보 숫자 쓰는 법과 가정법은 필수일까?입니다. 다음 글: AIC 입문: 강한 연결과 약한 연결을 번갈아 이으면 무엇을 지우나요?.

예제 판은 sudoku-core 생성기와 논리 풀이기로 찾은 자작 판이며, 시드·난이도·단계 번호는 메타에 기록했습니다. 정의 참고: HoDoKu Uniqueness.