스도쿠는 재미있는 게임이다. 9 * 9 칸 안에서 한 세로줄, 한 가로줄, 한 블록(3*3 칸, 여기서는 ’블록’이라는 표현을 쓰겠음) 안에 1부터 9까지의 자연수가 겹치지 않도록 배열하는 규칙 내에서 모든 칸의 수를 채우는 게임이다.
예)
| 9 | 1 | 5 | ||||||
|---|---|---|---|---|---|---|---|---|
| 2 | 5 | 3 | 1 | |||||
| 4 | 9 | 8 | 2 | |||||
| 7 | 2 | 5 | 9 | 8 | 4 | |||
| 1 | 9 | 5 | ||||||
| 5 | 9 | 2 | 7 | 3 | ||||
| 1 | 4 | 5 | 9 | 6 | 3 | |||
| 6 | 1 | 5 | 9 | |||||
| 8 | 7 | 5 |
정답은 아래와 같다.
| 9 | 3 | 6 | 2 | 1 | 8 | 7 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|
| 8 | 2 | 4 | 7 | 5 | 3 | 1 | 9 | 6 |
| 5 | 1 | 7 | 4 | 9 | 6 | 8 | 3 | 2 |
| 7 | 6 | 2 | 5 | 3 | 1 | 9 | 8 | 4 |
| 3 | 8 | 1 | 6 | 4 | 9 | 2 | 5 | 7 |
| 4 | 5 | 9 | 8 | 2 | 7 | 6 | 1 | 3 |
| 1 | 4 | 5 | 9 | 6 | 2 | 3 | 7 | 8 |
| 6 | 7 | 3 | 1 | 8 | 5 | 4 | 2 | 9 |
| 2 | 9 | 8 | 3 | 7 | 4 | 5 | 6 | 1 |
이와 같이 빈 숫자들을 모두 채우는 것이 스도쿠의 목표이다.
필자는 평소 스도쿠를 풀 때 몇 가지 규칙대로 하면 빠른 시간 안에 스도쿠를 해결할 수 있다는 것을 발견했는데, 그 규칙은 다음과 같다.
- 한 블럭 내에서 어떤 숫자가 들어갈 수 있는 곳이 한 곳 밖에 없다면 그 숫자를 확정한다.
- 한 세로줄 내에서 어떤 숫자가 들어갈 수 있는 곳이 한 곳 밖에 없다면 그 숫자를 확정한다.
- 한 가로줄 내에서 어떤 숫자가 들어갈 수 있는 곳이 한 곳 밖에 없다면 그 숫자를 확정한다.
이 알고리즘으로 스도쿠를 푼다면 ‘쉬운’ 스도쿠는 해결이 가능하다. (이 규칙으로 해결할 수 있는 스도쿠를 쉬운 스도쿠라고 생각한다. 몇몇은 정답이 여러 개고 몇몇은 숫자를 가정하지 않으면 풀 수가 없어서 그런 문제는 놔두고 이 방법으로 풀 수 있는 스도쿠부터 걸러내겠다.)
다음 글에서는 쉬운 스도쿠를 해결하는 코드를 설명하겠다.
[Python] 스도쿠 풀이 프로그램 #2 - https://fclipse.tistory.com/m/21
[
[Python] 스도쿠 풀이 프로그램 #2
‘쉬운’ 스도쿠를 풀 수 있는 스도쿠 알고리즘을 알아보자. 먼저 원리는 다음과 같다. 1. 빈칸이 있는 스도쿠를 입력받는다. 2. 숫자가 없는 빈칸(가능성 칸)에 각각 들어갈 수 있는 수들을 채워 준
fclipse.tistory.com