스도쿠(数独, Sudoku) - Revisited

PUBLISHED 2008.09.23 22:33
POSTED IN 놀이터
예전에 스도쿠(数独, Sudoku)가 무엇인지, 또 스도쿠(数独, Sudoku)의 해법은 어떻게 되는지에 관해 글을 남긴 적이 있습니다. 당시만 해도 처음 스도쿠를 접하던 시절이라 어떻게 풀이해야 하는가에 관해 체계적으로 접근하지 못했었고 단순히 보이는대로 문제를 해결해 나가던 시절이었습니다.

하지만 그런 단순한 해법으로는 고난이도의 문제를 해결하기에 힘들다는 것을 금방 깨닫게 될 것입니다. 그래서 이번에는 각 칸에 적합한 후보를 표시하는 방식을 통해 문제를 해결하는 방법을 살펴 볼까 합니다.

이제 후보가 될 게임을 하나 선정하겠습니다.


준비

이를 다음과 같이 조금 손을 봅니다. 비어있는 칸에 1부터 9까지의 숫자를 조그마하게 표시하는 것입니다. 이는 비어있는 칸에 들어갈 수 있는 후보가 1부터 9 모두가 된다는 의미입니다.

하지만 스도쿠(数独)의 룰에 따르면 각각의 가로줄(행)에는 1부터 9 사이의 숫자가 중복되는 일 없이 들어가야 합니다. 그에 따라 후보가 될 수 없는 숫자를 지워 나갑니다.

마찬가지로 각각의 세로줄(열)에 있어서도 1부터 9 사이의 숫자가 겹치는 일 없이 들어가야 합니다.

마지막으로 9개의 서브매트릭스 내에서도 1부터 9 사이의 숫자가 겹치지 않게 들어가야 합니다.


1단계

준비 단계가 끝나고 나면 비어있는 칸들 중에서 후보가 될 숫자가 하나만 남아 있는 곳이 나타납니다. 아래 그림에서 붉은색 음영으로 표시한 셀이 그런 경우입니다.

후보가 하나밖에 될 수 없는 곳에는 바로 그 숫자를 채워 넣습니다.

숫자를 채워넣으면 이로 인해 주변에 있는 다른 셀들도 영향을 받습니다. 준비 단계에서 했던 일을 다시 해 주면 됩니다. 각각의 행과 열, 서브매트릭스에서 1과 9 사이의 숫자가 중복되지 않도록 해 주는 것이지요.

이런  단계를 기계적으로 반복해 나갑니다.


2단계

하지만 어느 순간 후보가 하나인 빈 칸이 전혀 발생하지 않는 때가 올 것입니다. 이때는 시야를 서브매트릭스로 옮깁니다. 3 x 3 서브매트릭스에는 각각의 셀마다 둘 이상의 숫자가 표시되어 있을 것입니다.

하지만 이걸 떠올려 봅시다. 하나의 서브매트릭스에는 1부터 9 사이의 숫자가 단 하나만 존재해야 합니다. 빈 칸에 적힌 숫자들을 찬찬히 훑어 봅니다. 그 중 서브매트릭스에서 단 하나만 적힌 숫자가 있을지도 모릅니다.

맨 왼쪽 위 서브매트릭스를 살펴 보겠습니다. 일단 자리가 정해진 숫자는 1, 2, 6, 이렇게 세 개 밖에 없습니다. 3, 4, 5, 7, 8, 9, 이렇게 여섯 개의 숫자는 아직 제 자리를 정하지 못했습니다. 그런데 가만히 들여다 보니 1, 2, 6이 놓은 곳 말고 나머지 여섯 개의 빈 칸 중에서 9는 후보로 단 한 번만 적혀 있습니다. (그림에서는 1행 2열에 표시되어 있습니다.) 즉, 맨 왼쪽 위 서브매트릭스에서 9가 들어갈 수 있는 자리는 하나 밖에 없다는  뜻이지요. 이런 식으로 다른 서브매트릭스도 검사합니다.

이렇게 하면 다시 1단계에서 실시했던 과정을 거칠 수 있습니다.


1단계 과정이 제대로 되지 않으면 다시 2단계 접근 방식을 이용합니다.


3단계

이렇게 해서도 결론이 나지 않을 때에는 각 행과 각 열에 대해서도 특정 숫자가 후보로 들어간 경우가 단 하나뿐인 곳을 찾습니다.

다음 그림에서 4열을 살펴 보겠습니다. 이미 2, 7, 9가 자기 자리를 찾았고 나머지 숫자들의 자리를 찾을 때입니다. 이때 4열 8행을 보면 검은색으로 표시한 3이 눈에 띌 것입니다. 이는 4열 전체에서 3이 후보로 표시가 된 셀은 8행 하나 밖에 없다는 의미입니다.



이번에는 각 행을 살피면서 동일한 과정을 반복합니다.

이러다 보면 각 셀이 자신의 주인을 찾게 됩니다.

어때요, 간단하죠? ^ ^