앞에서 Naked Pair에 대해 살펴보았는데, 이번에 살펴볼 것은 그와 유사한 Naked Triple이다.

사실 Naked Pair와의 차이점은 숫자의 개수 말고는 없다.


위와 같이 똑같은 3개의 숫자로 이루어진 숫자가 같은 줄, 행, 블록 안에 있으면, 나머지 칸에는 그 숫자가 들어갈 수 없다는 것이다.

그림을 보면 1,2,3이 3개의 칸에 똑같이 들어가 있으며, 나머지 빨간색 칸에는 1,2,3이 들어갈 수 없다.

한가지 주의할 점은 위의 예와 같이 123이 동시에 3개의 칸에 등장할 때 이외에도,
아래의 예처럼 (12), (23), (13) 과 같은 식으로 3개의 숫자가 꼬리에 꼬리를 무는 형태로 나타나거나,
(123),(12),(13).
(12),(23),(123).
과 같은 식으로 나타나 있더라도 여전히 Naked Triple을 적용할 수 있다는 사실이다.

생각해보면 당연하지만, 위에서 이야기한 어떤 경우도 노란색 칸에 각각 1과 2와 3이 하나씩 들어갈 수밖에 없다는 점은 변함이 없으며, 따라서 나머지 빨간색에는 해당 숫자가 들어갈 수 없다는 것이다.

실제 예를 통해 알아보자.

위의 표시된 5번째 블록을 보면, 좌측 아래 노란색으로 표시된 3개의 칸에 3,6,7이 각각 쌍을 이루어 들어가 있음을 볼 수 있다. 따라서 5번재 블록 중, 노란색 블록을 제외한 곳에는 3,6,7이 들어갈 수 없으며, 해당 숫자를 지워 줘야 한다.


저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by 나일레

Naked Pair는 2개의 숫자가 짝을 이뤄서 같은 행, 같은 열, 같은 블록에 나타나는 것을 말한다.


빨간색으로 표시된 줄에, 1과 2의 쌍이 들어가 있다.

위와 같은 경우, 노란색으로 표시된 쌍을 제외한 나머지 빨간색 칸에는 1과 2가 들어갈 수 없다.

혹시라도 '왜?'라고 물으실 분을 위해 설명을 하자면,
1과 2는 모두 같은 줄에 표시가 되어 있으며, 위와 같이 쌍을 이루는 노란색 칸은 1과 2 이외에는 들어갈 수 있는 숫자가 없다. 따라서 노란색 칸 둘 중 하나에는 반드시 1이 들어가야 하며, 나머지 하나에는 2가 들어갈 수밖에 없다. 당연히 같은 줄의 나머지 칸에는 1과 2가 들어갈 수 없는 것이다.

만약 빨간색으로 표시되어 있는 칸에 1과 2가 들어갈 수 있다고 표시가 되어 있다면 이것들을 전부 지워줘야 한다.


실제 퍼즐의 예를 보자.
들어갈 수 있는 숫자의 표시를 모두 끝낸 후, 6번째 줄을 보니 1열과 6열에 6,9의 쌍이 있다.
따라서 빨간색으로 표시된 줄에는 노란색 칸 이외에 6,9가 들어갈 수 없다.

다음과 같이 다른 칸에 표시된 6과 9를 지워준다.


저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by 나일레

지금까지 기본 테크닉에서는, 따로 표시를 하지 않고 눈으로만 할 수 있는 방법을 알아보았는데,

기초 테크닉에서는 본격적으로 표시를 한 이후, 표시된 숫자를 이용하여 퍼즐을 풀어나가는 방법을 알아보도록 한다. 물론 표시된 숫자를 이용해서 추론을 하기 전에 가장 중요한 전제조건이 있다.

매우 중요하고 당연하지만, 그만큼 실수가 잦은 부분인데

표시해놓은 숫자에 잘못된 것이 없어야 한다는 것

이다.



문제를 풀 때, 위와 같이 미리 표시를 해 두고 풀게 되는데,
표시한 부분에 실수가 있으면, 잘못된 표시를 이용해서 한 추론은 거의 모두 잘못된 결과를 가져오므로, 표시를 할 때 신중하게 하는 것이 중요하다.

사람마다 다르겠지만 스도쿠 문제를 풀 때, 보통 다음의 과정을 따르게 된다.

① 스도쿠 문제를 훑어보고, Cross-hatching을 이용해 채울 수 있는 칸이 있으면 모두 채운다.

② Cross-hatching을 1~9까지의 숫자에 적용하여 모두 한번씩 해보았더라도, 새로 채워진 칸 때문에 다시 다른
    곳의 숫자를 알아낼 수 있는 경우가 있으므로, 한번 했다고 끝내지 말고, 더이상 크로스 해칭으로 알아낼 수 있
    는 숫자가 없을 때까지 반복해서 크로스 해칭을 통해 숫자를 알아낸다.

③ 더이상 크로스 해칭을 통해 알아낼 수 있는 숫자가 없으면, 위와 같이 모든 칸에, 각 칸에 들어갈 수 있는 숫자
    를 적는다.

④ 적은 결과 중에서 Naked Single을 찾는다.

※ Naked Single
앞에서 설명했다시피 각 행, 열, 블록에서 하나밖에 없는 숫자를 찾는다.
위의 퍼즐의 9번째 행을 눈여겨보면, 9행의 모든 칸 중에 6열의 칸만 3이 들어갈 수 있다.
사실 눈으로만 보아도 찾아낼 수 있는 부분이지만, 위의 경우와 같이 간혹 놓치는 경우가 있으므로 표시를 한 후 다시한번 꼼꼼히 훑어보고 찾아낸다.

④ 나머지를 가지고 앞으로 설명할 테크닉을 적용하여 문제를 풀어나간다.
저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by 나일레

크로스 해칭 또한 굉장히 기본적이고, 당연한 방법 중 하나다. 일단 다음의 퍼즐을 보면,


이런 식으로 제일 처음 퍼즐을 보게 되면, 기본적으로 주어진 숫자 외에 어떤 숫자부터 채워나가야 할 것인지 망설여지게 되는 분들이 많을 것이다. 퍼즐을 어떻게 풀기 시작하는지는 사람마다 서로 다른 방법이 있으므로, 무엇이 제일 낫다고 말하기는 어렵지만, 대부분의 경우 최초에 퍼즐을 보았을 때 크로스 해칭을 사용하게 된다.

크로스 해칭은 숨겨진 숫자(Hidden Single)를 알아내는 방법이다. 여기서 숨겨진 숫자라고 하는 것은, 문제에서 기본적으로 주어지지는 않았지만, 주어진 것과 다름없는 숫자를 말한다. 이게 무슨 말인지 초심자분들은 감이 잘 안 잡히실 텐데, 알아보기 쉽게 하기 위해 색칠을 좀 해 보았다.

위의 퍼즐에서 숫자 7에 주목하자.


빨간색으로 표시된 자리는 이미 그 행과 열에 7이 들어가있어서 빈칸이어도 7이 들어갈 수 없는 자리다.

여기서 3번째 블록을 보자. 3×3의 블럭 안에 1부터 9까지의 숫자가 전부 한번씩 들어가야 하므로, 당연히 3번째 블록에도 7이 들어가야 한다. 그런데 빨간색으로 표시된 곳을 보면 알다시피, 다른 행, 열에 이미 7이 들어가 있어 7이 들어갈 수 없는 자리를 빼고 나면 결국 3번째 블록에서 7이 들어갈 수 있는 자리는 남아있는 흰색 자리밖에 없게 된다. 이런 것은 문제에서 미리 주지는 않았지만, 별로 수고를 들이지 않고도 가장 먼저 찾아낼 수 있다.


비슷한 방법으로, 5번째 블록에서도 7의 위치를 확정지을 수 있다.
5번째 블록의 빈 칸 중, 5번째 행, 6번째 행의 빈 칸은 이미 다른 곳에 7이 들어가 있으므로 7이 들어갈 수 없다.
마찬가지로, 4열의 빈칸도 이미 다른 곳에 7이 들어가 있으므로 7이 들어갈 수 없다.
7이 들어갈 수 없는 자리를 빨간색으로 칠하고 나면, 5번째 블록에서 7이 들어갈 수 있는 자리는 4행 6열의 한 자리밖에 남지 않게 된다.

스도쿠 문제를 풀 때는 이런 포인트를 보통 가장 먼저 채우고 본격적인 풀이를 시작하는게 일반적이다.
위에서는 7을 예로 들었지만, 위 문제에서 7외에도 크로스 해칭을 적용할 수 있는 숫자가 더 많다.

굳이 하나하나 말로 설명하지는 않을 테니 한번 찾아보시길.



크로스 해칭을 할 때는 위와 같이 칸 단위로 볼 때도 있지만, 위의 예와 같이 행이나 열 단위로 볼 때가 있다.
초록색으로 표시된 6열을 보면, 마지막의 7,8행 자리만 빈칸이고 나머지 칸이 전부 채워져 있으며, 6열에는 9가 들어가 있지 않아 남은 두 칸 중 하나에는 무조건 9가 들어가야 한다.
여기서 8행을 보면 8행에는 이미 9가 들어가 있으므로, 8행 6열에는 9가 들어갈 수 없고 자연스럽게 흰색으로 표시된 7행 6열에 9가 들어갈 수밖에 없게 된다.

위와 같은 방법으로, 표시되지는 않았지만 미리 주어져 있는 것과 다름없는 숫자를 본격적으로 퍼즐을 풀기 전에 찾아내는 방법을 크로스 해칭이라고 하며, 모든 스도쿠 문제에서 가장 먼저 사용되는 테크닉 중 하나다.
저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by 나일레

스도쿠 문제를 풀다 보면, 필연적으로 빈 칸에 무엇이 들어갈 수 있는지를 연필로 표시해놓게 된다.
(어지간히 기억력이 좋으신 분이 아니라면 대부분 표시를 해가면서 문제를 풀게 될 것이다)

아직 감이 안 잡히시는 분을 위해서 예를 들어보자.


위와 같이 빈 칸에 들어갈 수 있는 숫자를 써 놓는 것이 기본적인 풀이 테크닉이다.

이렇게 표시를 해 놓는 것은 앞으로 알아볼 테크닉에서 매우 중요한 역할을 하게 되지만,

기본 테크닉에서는 연필로 표시(Pencil mark)를 할 필요가 없는 방법만을 알아보기로 한다.

풀 하우스는 가장 기본적인, 어찌보면 테크닉이라고 말하기도 좀 민망한 방법이다.


스도쿠는 그 룰에 따라, 가로줄, 세로줄, 한 개의 3×3 사각형에는 1부터 9까지의 숫자가 단 한개씩밖에 들어갈 수 없다. 이 당연한 룰에 따라, 나머지 하나를 채워넣는 것이 풀 하우스다.

사실 설명하고 말고 할 것도 없는 방법이지만, 언제나 기본이 중요한 것이다.


위의 스도쿠 퍼즐에서, 빈 칸에 들어갈 수 있는 숫자는 4가 된다.


당연하게도, 위에 표시된 나머지 빈칸도 같은 방법으로 숫자를 채울 수 있다.

사실 더이상 설명할 것도 없는 방법이라, 이쯤에서 포스팅을 마친다.
저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by 나일레

SUDOKU - Backgrounds

스도쿠 2011.02.22 16:48
1. 스도쿠의 역사

스도쿠의 역사는 1892년까 지 거슬러 올라간다. 프랑스의 일간지 《Le Siècle》가 두자리 숫자를 이용한 스도쿠와 같은 방식의 퍼즐을 게재했다. 1895년에는 다른 일간지 《La France》가 한 자리 숫자로 9×9의 바둑판을 채우는 퍼즐을 게재했지만, 여기선 3×3블록 룰은 없었다. 이 퍼즐들은 이따금 프랑스 몇몇 신문에 매주 게재되었지만 얼마 안 가서 제1차 세계대전 전후로 그 모습이 사라졌다.

스도쿠(Sudoku)는 18세기 스위스 수학자 레온하르트 오일러가 창안한 Latin Square 를 기반으로 하여 1979년 당시 74세의 건축가였던 미국의 Howard Garns가 현재의 모습으로 변형하여 1979년 5월 미국의 '델 매거진즈'(Dell Magazines)가 잡지 《Dell Pencil Puzzles & Word Games》에 "Number Place"로 소개된 것이 시초이나, 1984년 4월 일본의 출판사인 '니코리'(ニコリ, Nikoli)가 출판한 잡지 《퍼즐 통신 니코리》(パズル通信ニコリ)에 '스도쿠'라는 이름을 붙여 수록하면서 대중에게 보급되기 시작하여 2005년 무렵에 이르러 온 세계로 퍼져 나갔다.

- Wikepedia 에서 발췌.


2. 스도쿠라는 이름의 유래

'숫자는 한 번씩만 쓸 수 있다.'
数字は独身に限る
일본어인데, 이를 읽으면 '지와 도쿠신지 가기루' 가 된다.
스도쿠 자체가 일본에서 시작된 퍼즐이므로, 자연스럽게 일본어가 이름의 유래가 되었다.


3. 기본적인 룰


모든 스도쿠 퍼즐은 기본적으로, 다음과 같은 룰이 있다.

① 가로줄 하나에는 1~9까지의 숫자가 각각 하나씩밖에 들어갈 수 없다.
② 세로줄 하나에는 1~9까지의 숫자가 각각 하나씩밖에 들어갈 수 없다.
③ 각각의 3×3 사각형 하나에는 1~9까지의 숫자가 각각 하나씩밖에 들어갈 수 없다.

위 룰에 어긋나지 않도록, 숫자를 배열시켜 모든 칸에 알맞은 숫자를 찾아서 넣는 것이 스도쿠 게임의 목적이다.


4. 추가적인 룰

이 추가적인 룰은, 스도쿠가 게임으로서 성립하기 위해 필요한 룰이다.

모든 스도쿠 퍼즐은 단 하나의 해답만 있어야 한다.

모든 스도쿠 문제를 만들 때에는, 그 문제에 단 하나의 해답만이 존재하도록 만들어야 한다.
2가지 이상의 정답이 있는 문제는 올바른 스도쿠 문제가 아니다.
실제로 스도쿠 문제라고 주는 퍼즐들은 전부 정답이 하나밖에 없다.

'모든 스도쿠는 단 하나의 정답만을 가진다' 라는 것을 이용하여 역으로 문제를 풀어내는 방법도 있다.
(차후에 풀이 테크닉을 소개하면서 자세히 다룰 것이다.)


5. 스도쿠의 난이도

스도쿠의 난이도는 정확히 처음에 제시해 준 숫자의 개수와 비례하지는 않지만,
대체로 처음에 제시된 숫자가 많을수록 쉽고, 적을수록 어렵다.

현재 정답이 유일한 스도쿠 문제를 만들기 위해서는 최소 17개의 숫자를 먼저 제시해야 한다고 한다.
이렇게 두루뭉술하게 말하는 이유는, 딱히 어떤 수학적인 증명을 통해 나온 숫자는 아니기 때문이다.

17개의 숫자를 이용해서 퍼즐을 만들었을 때, 정답이 유일한 경우의 가짓수는 48826 개라고 알려져 있으며, 16개의 숫자를 이용했을 경우는 정답이 유일한 것이 단 한 개도 없다. (아직까지는)



그럼 다음 포스트부터는 본격적으로 스도쿠 풀이를 위한 테크닉을 차근차근 알아보도록 한다.
저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by 나일레
1. 시작하기 앞서.

최근 오며가며, 스도쿠를 하는 데에 다시 재미를 많이 붙였다.

스도쿠를 본격적으로 시작한 것은 군대에 있을 때인데, 무료한 말년에 할 게 없어서 시작했었다.

전역 후 자연스럽게 잊혀지는 듯 하다가, 최근 다시 시작한 것이다.

이 카테고리는 스도쿠에 관한 정보, 이를테면 역사, 룰, 풀이 테크닉 등에 대한 글로 채워질 예정이다.

언제 끝나게 될지 알 수 없고, 얼마나 쓰게 될지도 알 수 없지만, 현재 인터넷상에 제대로 된 스도쿠 관련

글은 거의 없는 것 같아서, 쓸 결심을 굳히게 되었다.


2. 업데이트

이 카테고리의 글은 상당히 불규칙적으로, 일관성없이 업데이트될 것 같다.

필자의 귀찮음이 가장 큰 이유겠지만, 그래도 언젠가 완성시킬 예정.


3. 용어

이 카테고리의 포스팅에 사용될 용어는 상당수가 영어가 될 것이다.

스도쿠 풀이 테크닉은 여러 가지가 있는데, 그 중 대부분이 영어 용어이고, 우리말로 적절한 표현을 찾지 못했을 경우 그대로 영어로 쓸 예정이다. 불편하시겠지만, 필자가 번역가가 아니므로 새로운 용어를 만들어서 적용시키기엔 무리가 좀 있다. 넓은 아량으로 이해해 주시길 바란다.


4. 스도쿠 문제를 구하는 법

스도쿠 문제는 꽤나 쉽게 구할 수 있다.

시중에 스도쿠 문제를 모아서 낸 책도 상당수 팔리고 있으며, 신문지상에 (특히 지하철 무료일간지나 스포츠신문)

종종 제공된다.

그 외에도, 외국에 매일 다양한 난이도의 스도쿠 문제를 제공하는 웹사이트가 있다.

Daily Sudoku 링크

Daily Sudoku 라는 곳인데, 위의 링크로 접속하면, 좌측에 Today's sudoku 메뉴가 있다.

난이도는 무난한 편. 회사에서 할 일 없으신 분은 프린트하셔서 잠깐잠깐 즐기시기에 좋을 듯하다.
저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by 나일레


티스토리 툴바