스도쿠 Gordonian Logic

출처 : http://flogsta.tistory.com/679

스도쿠 풀이의 기초부터 기법에 대한 설명부터 해당 기법을 사용할 수 있는 풍부한 예제까지 들어있다. 읽어보니, 그동안 내가 사용해왔던 기법부터, 처음 들어보는 기법까지 다양하다. (그 중 어떤 것은 아직도 이해가 잘 안되는 것이 있다. 써보고 잘 되니까 쓰는 것뿐.^^)

 

그 중에서, 고도니안 로직(Gordonian Logic)이 인상적이다. 이 기법은 이 책의 저자인 피터 고든(Peter Gordon)이 창안했기에 자신의 이름을 따서 붙인 것인데, 이 책에서 해당 기법을 개발하게 된 상황을 설명하고 있다.

(아래부터 스도쿠 용어가 많이 등장하고 있습니다. 이를 이해하시려면 여기를 참고하세요.)

친구가 추측하지 않고서는 도저히 풀 수 없다고 투덜대면서 위와 같은 문제를 보여주었다고 한다. 보면 셀25,27,37에 6과9의 후보숫자가 있고, 셀35에는 6,8,9의 후보숫자가 있다.

여기서 이 책의 저자인 피터 고든은 다음과 같이 말한다.

이 모양을 아주 오랫동안 들여다보며 고심한 끝에 혁명적인 스도쿠 해법을 발견해 냈다. 매우 풀기 힘든 문제를 식은 죽 먹기로 바꾸는 방법! 나는 이 방법에 '고도니언 직사각형'이라고 이름을 붙였다.

그리고 그는 셀35에 8을 집어 넣는다.

셀35가 8이 될 수 밖에 없다는 이유는 다음과 같다.

여기서 만약, 셀35가 8이 아니라고 한다면, 이 상황에서는 답이 두가지가 나올 수 있다.

이렇게 되거나

이렇게 된다. 그것은 셀35가 8이 아니라고 가정했기 때문에, 네 개의 서로 마주보는 셀들이 다음과 같이 두개씩 짝을 짓는 형태의 사각형이 되기 때문이다.

그러므로, 위의 그림과 같이 두 개의 후보숫자가 마주보는 두 쌍의 셀에 들어 있는 상황을 피해야한다.는 것이 고도니안 로직의 핵심이다. 

"스도쿠의 답은 오직 한 개만 존재한다"는 불문율을 이용한 것이다. 정말 창의적이지 않은가?

물론, 전문가가 만든 것이 아니라 미숙한 사람이 만들어서 답이 두 가지 이상 나올 수 있는 스도쿠 문제라면, 이러한 고도니안 로직이 통하지 않는다.

하지만 우리가 푸는 대부분의 스도쿠문제는 답이 하나만 나오도록 설정된 것이 대부분이므로, 풀다가 막힐 때 고도니안 로직을 이용하면 너무나 쉽게 문제가 풀리는 것을 경험하게 된다.

내가 풀어본 문제 중에서 고도니안 로직을 이용한 한가지 예를 들어보겠다.

거의 다 풀었는데 두 개씩 남은 짝들이 서로 얽혀 있어서 해결이 쉽지 않은 상황이다. 그러던 중, 빨간색 동그라미를 친 부분이 눈에 들어왔다. 고도니안 로직이다!

하지만 이대로 적용하려니 좀 부족한 듯하다. 27,27,27,267 이나 27,27,27,278의 형태로 되어있다면 고도니안 로직의 전형적인 형태일텐데, 이건 약간 벗어나있다.

하지만 약간 더 생각해본다. 고도니안 로직에 따르면, 위 빨간색으로 표시한 네 개의 셀이 모두 27이 되는 상황을 피해야하고, 그러면 셀61이 8이 되거나 또는 셀63이 6이 되어야한다.

셀 61이 8이 되는 경우를 가정해보면, 셀51이 2가 된다.

셀63이 6이 되는 경우를 가정해보면, 셀53이 2가 된다.

 

셀61이 8이 되던, 셀63이 6이 되던,  셀51또는 셀53에 2가 존재하게 되므로, 같은 로우에 있는 셀59에는 2가 들어갈 수가 없는 것이다.

따라서 셀59의 후보숫자 중에서 2를 제거하면, 박스6에서 후보숫자2를 가진 셀은 셀49만 존재하므로, 셀49에 2를 써넣을 수 있게 되고, 그 뒤로는 저자인 피터 고든의 표현처럼 "마치 산책을 가는 것처럼 쉽게 풀린다."

놀랍지 않은가! 다음에 어려운 스도쿠 문제를 만나면 고도니안 로직을 꼭 써보도록 하자.