image

썸네일

image

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

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

먼저 원리는 다음과 같다.

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

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

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

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

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

코드는 다음과 같다.

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

[  

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

스도쿠 풀이 알고리즘. Contribute to siejwkaodj/Sudoku development by creating an account on GitHub.

github.com

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

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

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

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

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

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

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

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

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

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
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

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

image

&lt; 예시 1번 &gt;

image

&lt; 예시 2번 &gt;

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

hard 1)

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

image

&lt; 예시 3번 &gt;

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

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

다음 글:

https://fclipse.tistory.com/26

[  

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

저번 글에 이어 이 글에서는 어려운 스도쿠를 풀 수 있는 프로그램을 설명한다. 백트래킹을 이용해 이를 구현했고, 생각보다 정말 간단하게 구현이 되었다. 먼저 사용된 함수는 다음과 같다. def

fclipse.tistory.com

](https://fclipse.tistory.com/26)