[프로젝트 오일러] Prob96 (스도쿠)

Sudoku.zip

 오일러 프로젝트 96번 문제(http://euler.synap.co.kr/prob_detail.php?id=96)를 풀기 위해 작성한 코드다.

 문제의 핵심은 당연하게도 스도쿠를 푸는 것이다.

 스도쿠를 풀기 위해서 사용된 알고리즘은 다음과 같다.

가. 유일 가능성을 갖는 자리를 찾고 존재 여부에 따라 다음을 실행한다.

 - 유일 가능성을 갖는 자리가 존재할 경우

   1. 해당 자리를 가능성이 있는 숫자로 확정한다.

   2. 숫자가 확정된 자리와 그에 영향을 받는 자리의 가능성을 제거한다.

   3. 다시 '가'를 실행한다.

 - 존재하지 않을 경우

   1. '나'를 실행한다.

나. 숫자가 확정되지 않은 자리가 있는지 확인한 후 존재 여부에 따라 다음을 실행한다.

 - 확정되지 않은 자리가 존재하지 않을 경우

   1. 문제가 풀린 경우이다. (End)

 - 존재할 경우

   1. '다'를 실행한다.

다. 숫자가 확정되지 않았으면서 가능성이 하나도 없는 자리를 찾는다.

라. '다'에서 찾은 자리가 있을 경우 가정 유무에 따라 다음을 실행한다.

 - 가정된 것이 없을 경우

   1. 문제가 잘못된 경우이다. (Error!)

 - 가정된 것이 있을 경우

   1. 최근에 행한 가정을 제거한다. (가정하기 전 풀이 상황으로 돌아간다.)

   2. (x, y)자리에서 n의 수를 가정했다고 할 경우, (x, y)자리의 n의 가능성을 없앤다.

마. 주어진 정보만으로는 풀이가 불가능하므로 가정을 한다.

   1. 현재 풀이 상황을 스택에 저장한다.

   2. 임의의 가능성 있는 자리를 찾는다.

   3. 해당 자리에 들어갈 수 있는 수 중 하나를 확정한다.

   4. 숫자가 확정된 자리와 그에 영향을 받는 자리의 가능성을 제거한다

바. '가'로 돌아간다.

* 유일 가능성이란 줄이나 상자에서 하나의 가능성만 갖을 경우를 의미한다.

Ex. 다음과 같은 상황에서 (9, 2)자리가 9라는 숫자로 유일 가능성을 갖는다.

[그 이유는 (9,2)자리가 (3,1)상자에서 유일하게 9의 가능성을 갖고 있기 때문이다.]

내 생각에 코드에서 개선해야 되는 부분은 2가지가 있다.

1. 한 자리에 하나의 가능성만 있는 경우를 확인하지 않았다. (현재는 가정으로 대신하고 있는거 같다.)

2. 가능성을 확인할 때 2중 for문으로 모든 자리를 확인하는게 아니라, 가능성이 변화된 부분을 중심적으로 확인하면 좋을거 같다.