[게임] Sudoku 공략

 가족여행을 떠날 때 비행기에서 하루종일 Sudoku를 풀며 논 적이 있다. 초/중급 단계는 어째어째 푸는데, 고급단계로 가면 어쩔땐 빨리 풀고, 어쩔 땐 어떤 수를 써도 못 푸는 상황이 발생하곤 했다.

 그래서 스도쿠를 완전히 풀 수 있는 알고리즘을 작성하기로 결심했다. 우선, 스도쿠 풀기에 내가 사용하는 방법은 가로를 보고, 세로를 보고, 9칸씩 보는 것이다(사실 이게 스도쿠의 규칙이다). 그래서 어떤 수가 있어야 하는 칸과 있으면 안되는 칸을 찾아내어 가며 확실한 칸에 숫자를 대입해 나가며 푼다. 

 (게임 사이트: http://sudoku-ko.com/)

 우선, 프로그램으로 작성하기 위해 각 칸에 1~9가 들어갈 수 있는 확률을 따져보면 좋지 않을까 생각했다. 그래서 9개의 숫자중 한 숫자가 칸에 들어갈 수 있는 확률이 1이 되었을 때, 그 숫자를 대입하고자 한다.

우선 간단히 생각하여 다음과 같은 로직을 구현하였다.

---

로직) 각 칸에 1~9가 들어갈 수 있는 확률을 구한다.

1-1) 윗 그림의 모든 1(가로), 2(세로), 3(정사각형)의 9개의 칸에 대해 1~9의 숫자가 나올 수 있는 확률을 조사한다.

=> 만약 9칸 중에 "1"이 있을 경우, 그 칸에서 "1"의 확률은 1이 되고, 다른칸에서 "1" 이 나올 수 있는 확률은 0이 된다.

=> 만약 9칸 중에 빈칸이 3개이고, 나오지 않은 숫자가 "1", "3", "5", "8" 이라면, 각 빈칸에서 "1", "3", "5", "8"이 나올 수 있는 확률은 1/4씩 이다.

1-2) 1, 2, 3 방법으로 구한 확률의 합을 더하여 3을 나눈다.

1-3) 확률이 1이 되는 숫자를 대입한다.

---

야~ 초급 클리어다! 위의 과정을 5번 반복하니 비어있던 칸이 채워지면서, 스도크 퍼즐을 완성할 수 있었다.

그런데 중급이상부터는 안풀리기 시작했다...

중급에서 각 숫자별 확률 분포를 살펴보자.

 0~1 사이의 색

분석해보니, 별표 친 부분과 같이, 분명히 확실함에도 불구하고 확률이 1이 되지 않아, 더이상의 풀이가 진행되지 않은 것을 알 수 있었다. 

이유는 가로, 세로, 정사각형을 각각 보는 방법을 취하였는데, 서로가 어떤 영향을 주는지에 대해 고려하지 않았기 때문이었다. 즉, 1, 2 방법으로 인해 3에서 값이 한개로 결정되는 경우가 발생한다는 것이다. 이를 고려하기 위해 로직을 수정하였다.

---

로직-수정) 각 칸에 1~9가 들어갈 수 있는 확률을 구한다.

1-1) 윗 그림의 모든 1(가로), 2(세로), 3(정사각형)의 9개의 칸에 대해 1~9의 숫자가 나올 수 있는 확률을 조사한다.

=> 만약 9칸 중에 "1"이 있을 경우, 그 칸에서 "1"의 확률은 1이 되고, 다른칸에서 "1" 이 나올 수 있는 확률은 0이 된다.

=> 만약 9칸 중에 빈칸이 3개이고, 나오지 않은 숫자가 "1", "3", "5", "8" 이라면, 각 빈칸에서 "1", "3", "5", "8"이 나올 수 있는 확률은 1/4씩 이다.

1-2) 1, 2, 3 방법으로 구한 확률의 합을 더하여 3을 나눈다. 

1-3) 1, 2, 3 방법 중 하나라도 확률이 0 이라면 최종 확률은 0이 되도록 하고 전체 확률이 1이되도록 재조정한다.

=>각 조건 1, 2, 3은 절대적인 게임 규칙이므로 각 1, 2, 3 방법 중 한 방법에서라도 어떤 수가 나올 확률이 0이라면 절대 나올 수 없는 숫자이다.

1-4) 확률이 1인 숫자를 칸에 대입한다.

---

중급에 성공했다!

그런데 상급은 또 안된다... 산넘어 산이네... 분석 해보자.

 0~1 사이의 색

각 칸 별 숫자들의 확률을 그래프로 나타낸 것이다. 빨간색으로 그룹진것을 보면 두개씩 두개씩 살아남아서 더이상 진행되지 않는 것을 알 수 있다. 실제 스도쿠 상급을 내가 풀어봐도 선택을 해야하는 경우가 발생한다. (선택지의 발생)

 일단은, 풀이 도중 두가지 선택지가 나타나 정체되었을 때, 한가지 선택지로 결정하여 문제를 풀고, 틀린 경우, 다시 선택지로 돌아와 나머지 선택지로 문제풀이를 계속해 나가도록 프로그램을 조정하여 상급문제를 풀 수 있도록 하였다.

 문제를 보고 프로그램에 숫자를 대입하고, 정답을 다시 문제 창에 입력하는 시간까지 합쳐서 1분 안에 문제를 풀 수 있었다. 실제 계산시간은 1초가 안걸리는 듯 싶다. 전략과 계산의 승리라고 할 수 있겠다.

 그러나 사실, 이 스도쿠를 프로그램을 통해 풀어보려고 했던 이유는 상급 문제를 풀다가 막혔을 때, 엄밀한 대답을 찾기 위해서였다. 각 숫자가 대입될 수 있는 확률을 살펴보면 해결할 수 있을거라 생각했는데 위와 같은 로직만으로는 한번에 문제를 풀수 없었다... 

 물론 선택지가 맞았을 경우에 그 뒤의 답이 슈루륵 계산 되기 때문에 훨씬 빠르게 풀 수 있지만, 왜 틀린 선택에 대해 찾아낼 수 없는 것일까? 라는 의문이 든다.

 어느곳에 둘지 선택하게 되는 상황은 적은 정보로 인해 발생하지만, 이 게임의 제약 조건 또한 정보이기 떄문에, 적은 정보는 더 적은 제약조건을 낳게 된다. 적은 정보로 인해 제약이 줄어든다면, 선택지에서 어느 선택지를 선택하든 답을 만들어 낼 수 있을것이다(답이 여러가지). 하지만, 3~4번 정도 상급문제를 풀어본 결과, 두가지 선택지 중 한가지는 바른길, 한가지는 잘못된 길이라는 것을 확인할 수 있었다. 실제, 스도쿠 문제를 만들 때도 가능한 정답은 한개뿐이 되도록 만들어진다고 한다(스도쿠에서 유일한 해를 가지기 위해 최소한으로 주어지는 숫자의 개수는 17개, 현재 갈림길에 봉착하는 상급문제에서 주어지는 숫자의 개수는 27개).

 스도쿠에서 주어지는 숫자는 답이 정해지는 제약조건이자, 문제를 풀게 해주는 정보가 된다. 우리는 거대한 정보들 사이의 규칙을 알고, 일부 정보들이 우리에게 주어진다. 우리에게 주어지는 정보로부터는 1개의 답이 주어지게되는데, 주어진 정보를 가지고 한번에 1개의 답을 찾아내지 못하고 여러번의 시도가 필요되어진다. 어떤 동굴이 있고, 이 동굴의 통로들에는 규칙이 있다고 쳤을 때, 우리에게 알고 있는 통로정보로는 한개의 동굴 지도밖에 그릴 수 없지만, 우리가 직접 알려지지 않은 통로를 지나보지 않으면 전체 동굴지도를 알 수 없는 상황에 봉착하게 된다고 비유볼 수 있다. 우리가 정한 3개의 규칙(가로, 세로, 정사각형에 1~9중 각각 1개의 값이 대입됨)이 서로 영향을 미치며 만들어낸 어떤 규칙을 우리가 놓치고 있어, 주어진 정보와 3개의 규칙만으로 전체정보를 추측할 수 없는 거라는 생각이 머리를 떠나지 않는다.

추가) 인터넷을 뒤져보면, 클래식 스도쿠(9x9)는 NP완전문제라고 알려져 있다. NP문제라고 찾아보니 자세한 내용은 어려워서 이해할 수 없었으나, 답이 한방에 딱 안나와서, 여러 경우의 수를 탐색하여 답을 찾아내는 방법 외에 딱히 뾰족한 수를 찾지 못하는 문제라고 한다.