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

썸네일

< 위는 스도쿠 입력을, 아래는 결과를 출력한 것 >

'쉬운' 스도쿠를 풀 수 있는 스도쿠 알고리즘을 알아보자.

먼저 원리는 다음과 같다.

 

1. 빈칸이 있는 스도쿠를 입력받는다.

2. 숫자가 없는 빈칸(가능성 칸)에 각각 들어갈 수 있는 수들을 채워 준다.

3. 행, 열, 블록(3 * 3 칸) 내에서 각각 가능성 칸에 있는 수가 유일한 수가 있다면 그

4. 이를 반복한다.숫자를 채운다.

 

이 알고리즘을 사용하면 가정이 필요한 스도쿠 이외의 모든 쉬운 스도쿠를 풀 수 있다.

 

코드는 다음과 같다.

https://github.com/siejwkaodj/Sudoku/blob/second/sudoku_2.py

GitHub - siejwkaodj/Sudoku: 스도쿠 풀이 알고리즘

 

새로 작성한 함수는 총 세 가지가 있다.

 

1. printMap() : 9*9 이차원 배열을 입력받고 출력해준다. 배열의 요소 중 일차원 리스트 까지는 형식에 맞춰(11칸) 출력해 줄 수 있다.

 

2. check_possibilities() : 비었거나(0) 리스트린 칸이 있다면 그 칸이 속하는 행, 열, 블록 내에서 가능한 숫자들로 그 칸을 채워 준다.

1부터 9까지 있는 리스트를 만든 다음, 반복문을 돌리며 행, 열, 블럭 내에 있는 수들을 리스트에서 지우고 남은 수들로 가능성을 확정한다.

 

3. check_onlyones() : 반복문을 돌며 리스트인 칸에서 가능한 수 중 그 칸이 속한 행, 열, 블록 내에 하나라도 그 칸에 들어갈 수밖에 없는 수가 있으면 그 수를 확정한다.

여기서 칸을 하나 확정하면 그 칸에 영향을 받는 다른 가능성 칸들을 수정해야 하므로 return을 통해 일단 반복을 종료하고 check_possibilities()로 가능성을 추가로 지워 준다.

 

 

코드의 나머지 부분은 while문으로 반복을 돌며 더 이상 추론이 되지 않을 때까지 가능성을 확인하고, 유일한 수를 확정한다.

 

예시로 사용된 스도쿠는 다음 두 종류가 있다.

 

1)

6			2	4			1
9	3	1		6	5		2	7
								3
4		7	5	8			3	2
		6	4					8
	8			1		7
3	5					8	7	1
8		9	3	7			5
7		2		5			4	9

 

2)

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

 

프로그램에 넣어 돌리면 다음 결과가 나온다.

 

&amp;lt; 예시 1번 &amp;gt;

&amp;lt; 예시 2번 &amp;gt;

하지만 다음 예시같은 경우는 완성이 불가능하다.

 

hard 1)

8
		3	6
	7			9		2
	5				7
				4	5	7
			1				3
	1						6	8
		8	5				1
	9					4

 

&amp;lt; 예시 3번 &amp;gt;

이런 스도쿠같은 경우는 경우의 수가 너무 많아 추론으로는 끝나지 않는다.

가정을 이용한 어려운 스도쿠를 푸는 코드는 다음 글에서 설명하겠다.

 

다음 글:

https://fclipse.tistory.com/26

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