신기한 퍼즐 속 비밀, 수학 퍼즐 스도쿠

2022-11-08
조회수 957


"스도쿠는 숫자 퍼즐 중 하나로, 매우 간단한  규칙이지만 해결하기 위해서는 상당한 시간과 노력, 사고력이 필요하다. 이러한 매력 때문에 전 세계인이 즐기는 유명한 퍼즐이 되었다. 스도쿠는 일반적으로 가로 9칸, 세로 9칸으로 구성되어 있고 규칙은 다음과 같다"


스도쿠 규칙

- 각 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩 들어간다.
- 굵은 선으로 나뉜(3×3) 크기의 표에도 1부터 9까지의 숫자가 한 번씩 들어간다.



스도쿠의 역사 

스도쿠의 역사를 거슬러 올라가면 그 끝에 우리가 매우 잘 알고 있는 수학자 오일러(Leonhard Euler: 1707~1783)가 있다. 오일러는 그의 논문에서 마방진과 비슷한 형태지만 숫자 대신 라틴 문자를 가로, 세로로 겹치지 않게 적은 방진(Square)을 사용하고 연구했는데, 이것이 라틴방진( Latin Square)이라는 이름으로 알려지게 되었다.


a
b
d
c
b
c
a
d
c
d
b
a
d
a
c
b


1979년, 미국의 하워드 간스(Howard Garns)는 오일러의 라틴방진을 기반으로 한 숫자 넣기(Number place)라는 이름의 퍼즐을 델(Dell)이라는 퍼즐 잡지를 통해 발표하였다. 이후 이 퍼즐이 일본에 알려지자, 1986년 일본의 잡지 회사 니코리(Nikoli)가 숫자 넣기 퍼즐을 ‘스도쿠’라는 이름으로 바꾸어 잡지에 수록하였다. 스도쿠라는 이름은 숫자(number)를 뜻하는 스(수, 數)와 단 하나(single)를 의미하는 도쿠(독, 獨)를 합하여 만든 단어로, ‘숫자들이 한 개씩 있다’라는 의미를 가진다. 이렇게 세계적으로 알려지기 시작한 후부터 지금까지 스도쿠는 다양한 형태로 변형되기도 하며 전 세계인의 사랑을 받는 퍼즐이 되었다.



스도쿠 속 비밀 

단순한 규칙의 스도쿠는 사실 매우 흥미로운 비밀을 지니고 있는 신비한 퍼즐이다. 그중 2가지 비밀을 소개하고자 한다.  9×9칸이라는 제한된 조건에서 얼마나 많은 스도쿠 퍼즐을 만들어낼 수 있을까? 그 수를 한 번 예상해 보자. 100가지? 10,000가지? 100,000가지? 여러분은 얼마나 많은 가짓수를 예상하는가? 

결론부터 말하자면 무려 6,670,903,752,021,072,936,960(66해 7090경 3752조 210억 7293만 6960)가지이다.

뒤집거나 돌렸을 때 같은 모양이 되는 경우를 제외하더라도 5,472,730,538(54억 7273만 538)가지나 된다. 이 경우의 수를 알아낸 사람은 독일의 컴퓨터 공학자 펠겐하우어(Bertam Felgenhauer)와 영국의 수학자 자비스(Frazer Jarvis)이다. 그들은 경우의 수를 구하는 아이디어와 컴퓨터를 활용하여 경우의 수를 구했고, 그 아이디어는 다음과 같다.


 ① 스도쿠를 3×3 크기의 블록 9개(B1~B9)로 나눈다.











B1


B2


B3




















B4


B4


B4




















B4


B4


B4












② B1 블록을 임의로 채운다.

 1
2
3
  4
5
6
  7
8
9


③ 임의로 채운 B1 블록에 따라 B2, B3 블록을 채우는 경우의 수를 구한다.


④ B4, B7 블록의 첫째 열을 채우는 경우의 수를 구한다.


⑤ 스도쿠의 나머지 칸을 채우고 경우의 수를 구한다.


스도쿠를 풀 수 있도록 문제를 만들기 위해서는 적어도 몇 개의 숫자 단서를 주어야 할까? 두 번째 비밀은 이 질문에서부터 시작한다. 스도쿠를 풀었을 때 답이 유일하게 나오도록 만들려면 단서가 너무 적으면 안 된다. 또 단서를 너무 많이 주면 난이도가 쉬워진다. 되도록 단서를 적게 주면서 답이 유일하게 나오도록 하려면 적어도 17개의 단서를 주어야 한다. 이 사실은 2012년, 아일랜드 더블린대의 게리 맥과이어 교수팀에 의해 증명되었다. 슈퍼컴퓨터를 동원하여 16개의 단서만으로는 스도쿠를 풀 수 없다는 사실을 증명한 것이다.



풀리지 않는 스도쿠의 비밀

스도쿠는 규칙이 매우 단순한 퍼즐임에도 불구하고 쉽게 풀리지 않게 문제를 만들 수 있다. 단순해 보이지만 쉽게 풀리지 않는 퍼즐, 이것이 스도쿠의 매력이자 오랜 시간동안 스도쿠가 많은 사람들에게 사랑 받고 있는 이유이다. 그렇다면 스도쿠를 쉽게 해결할 수 있는 해결법은 없을까? 결론부터 말하자면 모든 경우의 수를 확인해 보지 않는 이상 해결법은 없다. 

사실 스도쿠는 P-NP문제와 관련이 있다. P-NP 문제는 7대 수학 난제인 밀레니엄 문제 중 하나로, 아직까지 증명되지는 않고 있다. P는 주어진 시간 동안 쉽게 풀 수 있고 검산도 쉬운 문제를 의미하며, NP는 쉽게 풀 수는 없지만 답이 무엇인지만 알면 검산은 쉬운 문제를 의미한다. P-NP 문제는 NP 집합이 P 집합에 속하는지에 대해 묻는 문제로, NP 집합이 P 집합에 속한다면 NP 문제를 컴퓨터 알고리즘에 따라 빠른 시간 안에 답을 찾을 수 있게 되는 것이다. 

스도쿠는 NP 문제로, 검산은 쉽지만 쉽게 풀 수는 없는 문제이다. P-NP문제가 증명되지 않았으니, 아직까지 스도쿠는 쉽게 풀 수 있는 해결법이 없는 셈이다. 다만 문제를 잘 해결할 수 있도록 도와주는 여러 가지 전략이 있을 뿐이다. 자신만의 전략을 찾아 다음 스도쿠 문제를 해결해 보자.


8

2

4

6

9

5


8


2

4


5

9


3

4
3



5

1
7
2


9


6
8
9

1

3

4


3


2
6
7

4
5

6

5

8

9
7
4
1

2





I 글쓴이 와이즈만 영재교육연구소 수학팀 안혜원 선임연구원 


#융합시사상식 #스도쿠 #수학퍼즐  #숫자퍼즐 #와이즈만수학 #와이즈만사고력수학 #와이즈만영재교육






0 0