[Python] 스도쿠 풀이 프로그램 #1

스도쿠는 재미있는 게임이다.
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

이와 같이 빈 숫자들을 모두 채우는 것이 스도쿠의 목표이다.

필자는 평소 스도쿠를 풀 때 몇 가지 규칙대로 하면 빠른 시간 안에 스도쿠를 해결할 수 있다는 것을 발견했는데, 그 규칙은 다음과 같다.

1. 한 블럭 내에서 어떤 숫자가 들어갈 수 있는 곳이 한 곳 밖에 없다면 그 숫자를 확정한다.
2. 한 세로줄 내에서 어떤 숫자가 들어갈 수 있는 곳이 한 곳 밖에 없다면 그 숫자를 확정한다.
3. 한 가로줄 내에서 어떤 숫자가 들어갈 수 있는 곳이 한 곳 밖에 없다면 그 숫자를 확정한다.

이 알고리즘으로 스도쿠를 푼다면 '쉬운' 스도쿠는 해결이 가능하다. (이 규칙으로 해결할 수 있는 스도쿠를 쉬운 스도쿠라고 생각한다. 몇몇은 정답이 여러 개고 몇몇은 숫자를 가정하지 않으면 풀 수가 없어서 그런 문제는 놔두고 이 방법으로 풀 수 있는 스도쿠부터 걸러내겠다.)

다음 글에서는 쉬운 스도쿠를 해결하는 코드를 설명하겠다.

[Python] 스도쿠 풀이 프로그램 #2 - https://fclipse.tistory.com/m/21

[Python] 스도쿠 풀이 프로그램 #2