"스도쿠는 숫자 퍼즐 중 하나로, 매우 간단한 규칙이지만 해결하기 위해서는 상당한 시간과 노력, 사고력이 필요하다. 이러한 매력 때문에 전 세계인이 즐기는 유명한 퍼즐이 되었다. 스도쿠는 일반적으로 가로 9칸, 세로 9칸으로 구성되어 있고 규칙은 다음과 같다"
스도쿠 규칙
- 각 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩 들어간다. - 굵은 선으로 나뉜(3×3) 크기의 표에도 1부터 9까지의 숫자가 한 번씩 들어간다. |
스도쿠의 역사
스도쿠의 역사를 거슬러 올라가면 그 끝에 우리가 매우 잘 알고 있는 수학자 오일러(Leonhard Euler: 1707~1783)가 있다. 오일러는 그의 논문에서 마방진과 비슷한 형태지만 숫자 대신 라틴 문자를 가로, 세로로 겹치지 않게 적은 방진(Square)을 사용하고 연구했는데, 이것이 라틴방진( Latin Square)이라는 이름으로 알려지게 되었다.
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 블록을 임의로 채운다.
③ 임의로 채운 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 글쓴이 와이즈만 영재교육연구소 수학팀 안혜원 선임연구원
#융합시사상식 #스도쿠 #수학퍼즐 #숫자퍼즐 #와이즈만수학 #와이즈만사고력수학 #와이즈만영재교육
"스도쿠는 숫자 퍼즐 중 하나로, 매우 간단한 규칙이지만 해결하기 위해서는 상당한 시간과 노력, 사고력이 필요하다. 이러한 매력 때문에 전 세계인이 즐기는 유명한 퍼즐이 되었다. 스도쿠는 일반적으로 가로 9칸, 세로 9칸으로 구성되어 있고 규칙은 다음과 같다"
스도쿠의 역사를 거슬러 올라가면 그 끝에 우리가 매우 잘 알고 있는 수학자 오일러(Leonhard Euler: 1707~1783)가 있다. 오일러는 그의 논문에서 마방진과 비슷한 형태지만 숫자 대신 라틴 문자를 가로, 세로로 겹치지 않게 적은 방진(Square)을 사용하고 연구했는데, 이것이 라틴방진( Latin Square)이라는 이름으로 알려지게 되었다.
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 블록을 임의로 채운다.
③ 임의로 채운 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문제가 증명되지 않았으니, 아직까지 스도쿠는 쉽게 풀 수 있는 해결법이 없는 셈이다. 다만 문제를 잘 해결할 수 있도록 도와주는 여러 가지 전략이 있을 뿐이다. 자신만의 전략을 찾아 다음 스도쿠 문제를 해결해 보자.
I 글쓴이 와이즈만 영재교육연구소 수학팀 안혜원 선임연구원
#융합시사상식 #스도쿠 #수학퍼즐 #숫자퍼즐 #와이즈만수학 #와이즈만사고력수학 #와이즈만영재교육