스도쿠를 찍지 않고 푸는 기본 기법

스도쿠는 가로줄, 세로줄, 굵은 선으로 나뉜 3×3 상자마다 1부터 9까지 한 번씩 들어가게 채우는 퍼즐입니다. 규칙은 이것이 전부지만, 막혔을 때 무엇을 봐야 하는지 모르면 금세 찍기로 넘어가게 됩니다. 이 글은 추측 없이 풀기 위한 기본 기법 네 가지를 그림으로 설명하고, 이 사이트의 스도쿠가 그 기법들로 난이도를 어떻게 나누는지 코드를 기준으로 정리합니다. 난이도별 숫자는 게임과 같은 코드로 퍼즐을 직접 만들어 잰 값입니다.

한눈에 보기

우리 게임의 난이도는 이렇게 정해집니다

이 사이트의 스도쿠는 퍼즐을 만들 때마다 컴퓨터가 사람처럼 풀어 보고, 어떤 기법이 필요했는지로 난이도를 매깁니다.

1. 완성된 판을 하나 만든 뒤 숫자를 지워 나갑니다. 지울 때마다 답이 여전히 하나뿐인지 끝까지 검사하고, 답이 둘 이상이 되면 그 숫자는 되살립니다. 먼저 판의 중심을 기준으로 180도 돌린 위치의 두 칸을 한 쌍으로 지우고, 그래도 목표 개수까지 줄지 않으면 한 칸씩 지웁니다.
2. 남은 퍼즐을 네이키드 싱글과 히든 싱글만으로 풀어 봅니다. 끝까지 풀리면 1단계입니다.
3. 막히면 교차(상자 → 줄, 줄 → 상자)와 네이키드 페어, 히든 페어로 후보를 지우고 다시 싱글을 찾습니다. 이렇게 끝까지 풀리면 2단계, 그래도 막히면 3단계입니다.
4. 쉬움과 보통은 1단계, 어려움은 2단계이면서 주어진 숫자가 정해진 개수 이하인 퍼즐이 나올 때까지 최대 24번 새로 만들어 봅니다. 끝내 맞는 퍼즐이 나오지 않으면, 추측이 필요한 퍼즐보다는 쉬운 쪽을 내보냅니다.

설정된 주어진 숫자의 개수와, 난이도마다 500개씩 실제로 만들어 잰 결과는 다음과 같습니다.

실제 개수가 설정보다 하나 적은 경우가 있는 것은, 두 칸씩 짝지어 지우다 보면 목표를 한 칸 넘길 때가 있어서입니다. 어려움 500개 가운데 10개는 24번 안에 조건에 맞는 퍼즐을 찾지 못해 싱글만으로 풀리는 퍼즐이 나온 경우였습니다. 교차와 페어로도 풀리지 않는 3단계 퍼즐은 1,500개 가운데 하나도 없었습니다. 하루 동안 모두에게 같은 문제가 나오는 오늘의 스도쿠는 보통 난이도로 만들어집니다.

마지막 열이 보여 주듯 쉬움과 보통은 같은 기법만 쓰는데도 느낌이 꽤 다릅니다. 처음에 바로 채울 수 있는 칸이 쉬움은 20칸쯤, 보통은 11칸쯤이라 보통에서는 첫 실마리를 찾는 데 시간이 더 걸립니다. 주어진 숫자가 적을수록 대체로 어려워지지만 개수만으로 난이도가 정해지지는 않습니다. 참고로 답이 하나뿐인 스도쿠는 주어진 숫자가 적어도 17개 있어야 한다는 사실이 2012년 발표된 컴퓨터 전수 탐색으로 증명되었습니다.

네이키드 싱글: 칸을 보고 찾기

한 칸을 골라, 그 칸이 속한 가로줄·세로줄·상자에 이미 있는 숫자를 모두 지워 봅니다. 남는 숫자가 하나뿐이면 그 칸의 답입니다. 그림 왼쪽의 가운데 칸은 가로줄에 1·2·3, 세로줄에 4·5·6, 상자에 7·8이 있어 9만 남습니다.

네이키드 싱글은 이해하기 가장 쉽지만, 사람 눈으로 찾기는 의외로 어렵습니다. 한 칸마다 이웃 스무 칸(같은 가로줄 8칸, 같은 세로줄 8칸, 같은 상자에서 겹치지 않는 4칸)을 모두 훑어야 하기 때문입니다. 실제로 우리 게임의 보통 퍼즐 500개를 조사해 보니, 시작하자마자 네이키드 싱글인 칸은 평균 2.5칸뿐이었습니다.

히든 싱글: 숫자를 보고 찾기

히든 싱글은 방향을 바꿔 숫자 하나를 정하고 그 숫자가 들어갈 자리를 찾는 방법입니다. 그림 오른쪽에서 왼쪽 위 상자에는 아직 5가 없습니다. 첫째·둘째 가로줄에는 다른 상자에 5가 있고, 첫째·둘째 세로줄에도 아래쪽에 5가 있습니다. 이 네 줄에 걸리는 칸을 지우면 상자 안에서 5가 갈 수 있는 칸은 오른쪽 아래 한 칸뿐입니다. 그 칸 자체에는 1·3·4·5·6·9가 모두 들어갈 수 있어 네이키드 싱글로는 보이지 않지만, 5의 입장에서는 갈 곳이 여기밖에 없습니다.

보통 퍼즐에서 시작하자마자 채울 수 있는 칸은 평균 11.2칸이었는데, 그중 8.7칸은 네이키드 싱글이 아니라 히든 싱글로만 보이는 칸이었습니다. 어려움에서는 5.4칸 가운데 4.7칸이 그랬습니다. 그래서 막혔을 때는 칸을 하나씩 노려보기보다 숫자 하나를 정해 판 전체를 훑는 편이 빠릅니다. 우리 게임의 숫자판 아래 작은 숫자는 그 숫자가 몇 개 더 들어가야 하는지 알려 주니, 남은 개수가 적은 숫자부터 훑어보세요. 이미 많이 채워진 숫자일수록 남은 자리를 막는 줄이 많아 히든 싱글로 떨어지기 쉽습니다.

메모 쓰는 법

싱글이 더 보이지 않으면 메모(후보 숫자)를 적을 차례입니다. 우리 게임의 메모 기능은 이렇게 동작합니다.

• 메모 버튼이나 N 키로 메모 모드를 켜고 끕니다. 메모 모드에서 숫자를 누르면 칸에 작은 숫자가 적히고, 같은 숫자를 다시 누르면 지워집니다.
• Shift를 누른 채 숫자 키를 누르면 메모 모드와 상관없이 메모를 적거나 지울 수 있습니다.
• 정답을 넣으면 같은 가로줄·세로줄·상자의 메모에서 그 숫자가 저절로 지워집니다. 정답으로 들어간 숫자는 더 이상 지워지지 않습니다.
• 숫자가 들어 있는 칸을 고르면 판 전체의 같은 숫자와, 메모 속의 같은 숫자가 함께 강조됩니다.
• 틀린 숫자는 빨간색으로 표시되고 실수로 셉니다. '실수 3번이면 끝'을 켜 두면 세 번째 실수에서 게임이 끝나고, 되돌리기로 지워도 실수 횟수는 그대로입니다.

메모는 처음부터 모든 칸에 적을 필요가 없습니다. 효율적인 순서는 이렇습니다.

1. 싱글로 채울 수 있는 곳을 먼저 모두 채웁니다. 판이 최대한 차 있어야 적을 후보가 줄어듭니다.
2. 빈칸이 적은 줄이나 상자부터 메모합니다. 빈칸이 세 칸뿐인 줄이라면 남은 숫자 세 개만 따져 보면 됩니다.
3. 후보가 두 개뿐인 칸은 특히 눈여겨보세요. 뒤에 나올 페어가 여기서 시작됩니다.
4. 정답을 하나 넣을 때마다 이웃 메모가 자동으로 지워지므로, 후보가 하나만 남은 칸이 새로 생기지 않았는지 확인합니다.

교차: 상자와 줄이 겹치는 곳

어려움 퍼즐은 싱글만으로는 막히도록 골라 낸 것이라, 메모를 적은 뒤 후보를 지우는 단계가 하나 더 필요합니다. 그 첫 번째가 교차(locked candidates)입니다. 방향은 두 가지입니다.

• 상자 → 줄: 한 상자 안에서 어떤 숫자의 후보가 모두 같은 가로줄(또는 세로줄)에 있다면, 그 숫자는 그 줄 가운데 이 상자에 속한 부분에 반드시 들어갑니다. 따라서 같은 줄의 다른 상자에서는 그 숫자를 후보에서 지울 수 있습니다. 그림 ①에서 왼쪽 상자의 4 후보는 둘째 줄 두 칸에만 있으므로, 둘째 줄 오른쪽 상자의 4 후보 두 개를 지웁니다. 그러면 오른쪽 상자의 4는 셋째 줄 한 칸만 남아 히든 싱글이 됩니다.
• 줄 → 상자: 반대로 한 줄에서 어떤 숫자의 후보가 모두 한 상자 안에 있다면, 그 상자의 그 숫자는 반드시 이 줄에 들어갑니다. 따라서 같은 상자의 다른 줄에서는 그 숫자를 지울 수 있습니다. 그림 ②에서 첫째 줄의 7 후보는 가운데 상자 안의 두 칸뿐이므로, 가운데 상자의 둘째·셋째 줄에 있는 7 후보를 모두 지웁니다.

교차는 칸을 직접 채우지는 않지만, 후보를 지우고 나면 앞에서 본 싱글이 새로 생기는 경우가 많습니다. 우리 게임의 강조 기능을 쓰면 찾기가 쉬워집니다. 판에서 4가 들어 있는 칸을 하나 누르면 모든 4와 메모 속의 4가 함께 강조되니, 상자마다 강조된 메모가 한 줄에 몰려 있는지만 보면 됩니다.

페어: 두 칸이 두 숫자를 나눠 가질 때

• 네이키드 페어: 같은 줄(또는 열, 상자)에 후보가 똑같이 두 숫자뿐인 칸이 두 개 있으면, 그 두 숫자는 두 칸이 나눠 가집니다. 어느 칸이 어느 숫자인지는 몰라도, 같은 줄의 다른 칸에서는 두 숫자를 지울 수 있습니다. 그림 ①에서 둘째·다섯째 칸이 3과 8만 후보로 가지므로 셋째 칸의 3·8과 여섯째 칸의 8을 지우고, 셋째 칸은 6만 남아 확정됩니다.
• 히든 페어: 두 숫자가 같은 줄에서 똑같은 두 칸에만 들어갈 수 있다면, 그 두 칸은 그 두 숫자의 자리입니다. 두 칸에 적힌 다른 후보는 모두 지울 수 있습니다. 그림 ②에서 2와 7은 첫째·여섯째 칸에만 후보로 있으므로, 두 칸에서 1·4와 5·9를 지웁니다.

네이키드 페어는 '칸 두 개, 후보 두 개'가 눈에 보이는 대로 찾으면 되고, 히든 페어는 숫자마다 후보가 몇 칸에 있는지 세어 봐야 보입니다. 우리 게임의 퍼즐은 교차와 이 두 페어까지 쓰면 풀리도록 골라 낸 것이라, 세 칸이 세 숫자를 나눠 가지는 트리플이나 X-윙 같은 더 어려운 기법은 몰라도 됩니다.

막혔을 때의 순서

1. 남은 개수가 적은 숫자부터 히든 싱글을 찾습니다.
2. 빈칸이 적은 줄·상자에서 네이키드 싱글을 확인합니다.
3. 더 보이지 않으면 빈칸이 적은 곳부터 메모를 적습니다.
4. 상자와 줄이 겹치는 곳에서 교차를 찾아 후보를 지웁니다.
5. 후보가 두 개뿐인 칸끼리 네이키드 페어를, 두 칸에만 나오는 숫자 쌍으로 히든 페어를 찾습니다.
6. 후보가 줄었으면 1번으로 돌아갑니다.

흔한 실수

1. 찍어서 확인하기. 우리 게임은 틀린 숫자를 바로 빨갛게 보여 주지만, 찍어서 맞히면 실수 횟수만 늘고 풀이 실력은 늘지 않습니다. 답이 하나뿐인 퍼즐이므로, 막혔다면 놓친 단서가 있다는 뜻입니다.
2. 처음부터 모든 칸에 메모하기. 판이 비어 있을 때 적은 메모는 후보가 너무 많아 오히려 단서를 가립니다. 싱글을 다 채운 뒤에 적으세요.
3. 메모를 고치지 않기. 교차나 페어로 지울 수 있는 후보를 그대로 두면, 나중에 그 메모를 믿고 판단하다 틀립니다.
4. 한 칸만 노려보기. 네이키드 싱글만 찾다 보면 히든 싱글을 놓칩니다. 칸이 아니라 숫자를 기준으로 훑는 시간을 따로 가지세요.
5. 교차의 방향을 헷갈리기. 지우는 곳은 항상 '몰려 있는 쪽이 아닌 쪽'입니다. 상자 안의 후보가 한 줄에 몰렸다면 그 줄의 다른 상자에서, 줄의 후보가 한 상자에 몰렸다면 그 상자의 다른 줄에서 지웁니다.

연습 방법

• 쉬움에서 히든 싱글만 쓰기. 쉬움 퍼즐을 숫자 1부터 9까지 차례로 훑으며 히든 싱글만으로 풀어 보세요. 숫자를 기준으로 보는 눈이 길러집니다.
• 보통은 메모 없이 시간을 재며 풀기. 보통도 싱글만으로 풀리므로, 메모 없이 끝까지 가는 연습에 좋습니다. 기록이 줄어드는 만큼 단서를 찾는 속도가 붙었다는 뜻입니다.
• 어려움은 메모부터 천천히. 어려움에서는 싱글이 막히는 지점이 반드시 옵니다. 그때 메모를 적고 교차와 페어를 하나씩 찾아보세요.
• 오늘의 스도쿠로 겨루기. 오늘의 스도쿠는 하루 동안 모두에게 같은 보통 퍼즐이 나오니, 친구와 같은 문제로 시간을 겨뤄 볼 수 있습니다.

정리

스도쿠의 기본은 두 가지 싱글입니다. 칸을 보고 들어갈 숫자가 하나뿐인지 확인하는 네이키드 싱글, 숫자를 보고 들어갈 자리가 하나뿐인지 확인하는 히든 싱글입니다. 우리 게임의 쉬움과 보통은 이 둘만으로 끝까지 풀리고, 어려움은 메모를 적은 뒤 교차와 페어로 후보를 지워야 풀리도록 골라 낸 퍼즐입니다. 보통부터는 첫 실마리의 대부분이 히든 싱글이니, 남은 개수가 적은 숫자부터 판 전체를 훑는 습관을 들이세요. 설명한 기법은 스도쿠에서 바로 연습해 볼 수 있습니다.

참고 자료

• 위키백과: 스도쿠
• 위키백과: Sudoku
• McGuire, Tugemann, Civario. There is no 16-Clue Sudoku (arXiv:1201.0749)
• SudokuWiki: Naked Candidates
• SudokuWiki: Hidden Candidates
• SudokuWiki: Intersection Removal