이 글은 Udacity Artifical Intelligence Nanodegree의 Curriculum 1에 나오는 스도쿠 풀기 내용을 정리한 글입니다.

Image for post
Image for post
https://pixabay.com/images/id-412435/

먼저 간단한 방법으로 스토쿠를 풀어보자.

Elimination

번저 각 칸에 놓일 수 있는 값들을 아래처럼 정리한다.

Image for post
Image for post

Only Choice

Image for post
Image for post

이후 각 영역에서, 유일한 선택지를 찾아서 그것을 선택한다. 예를 들어 붉게 표시된 영역을 보면, 유일한 선택지는 1이다. 영역 안의 남은 값은 1, 4, 7, 9지만 1은 오직 오른쪽 위의 칸에만 적용될 수 있다. 이제 1을 선택한다.

Image for post
Image for post

이 방법을 문제가 풀릴 때까지 반복하는 방법이다.

더 어려운 문제들

위 방법은 아래와 같은 어려운 문제는 해결할 수 없다.

Image for post
Image for post

우리는 새로운 방법을 통해 이 문제를 풀어야한다. 간단한 검색을 통해 문제를 해결할 수 있다. 예를 들어 A2칸에 1을 놓은 뒤 문제를 풀어보고, 안되면 6을 놓고,, 이런 식으로 다양한 경우의 수를 체크해보는 것이다. 하지만 이것을 우리는 좀 더 똑똑하게 할 수 있다.

Search

Image for post
Image for post

위 붉게 친 4개의 칸을 보자. 어떤 칸을 선택해서 검색해보는게 효율적인가? G2가 효율적을 보이지 않는가? 그 이유는 G2의 선택 가능한 숫자가 가장 적은 2개이기 때문이다. 우리는 DFS나 BFS와 같은 방법으로 경우의 수를 트리 형태로 만들어서 검색할 수 있다.

Naked Twins

간단한 실습이 끝난 후 Diagonal Sudoku를 해결하기 위한 Naked Twins의 Pseudo Code가 나오고 이를 구현하는 프로젝트를 진행한다. Diagonal Sudoku는 기본 스토쿠에 정사각형의 X자 대각선 값들 또한 1~9사이의 값을 하나만 가져야하는 조건이다.

Image for post
Image for post

프로젝트 해결 코드는 아래 깃허브 repository에 있다.

Written by

2020.12.8 ~ 2022.6.9 군복무중 Serving in the South Korean Military Service

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store