스도쿠

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기
스도쿠 퍼즐의 예 (정답)
세로 칸(보라색)과 가로 칸(하늘색), 3×3 격자(연두색) 안 1~9까지의 숫자가 겹치지 않아야 한다. (정답)
킬러 스도쿠 (정답)
노노미노 또는 직소 스도쿠 (정답)
워도쿠 퍼즐 (정답)

스도쿠(일본어: 数独)는 숫자 퍼즐로, 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐이다. 숫자넣기로도 불린다. “숫자는 한 번씩만 쓸 수 있다”(数字は独身に限る 수'지와 독'신'니가길[*])[1]를 줄인 말로 2005년 전 세계적으로 이 말과 퍼즐이 퍼져나갔다. 퍼즐을 푸는 방법은 같은 줄에는 1에서 9까지의 숫자를 한 번만 넣고, 3x3칸의 작은 격자 또한 1에서 9까지의 숫자가 겹치지 않게 들어가야 한다.

역사[편집]

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

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

스도쿠의 수학[편집]

  • 가능한 모든 경우의 값을 구하였는데, 그 수는 6670903752021072936960 (66해 7090경 3752조 210억 7293만 6960) 개나 된다.(OEIS의 수열 A107739)[2]
  • 스도쿠 중에서는 풀리지 않는 문제도 있고, 답이 2개인 문제도 있다. 그래서 답이 1개인 문제를 만드는 것이 원칙이다.
  • 스도쿠 문제에서 유일한 풀이가 존재하는 문제의 숫자 개수의 최솟값은 17이다. 17개의 경우, 49000개가 넘는 스도쿠 문제가 알려져 있다. 증명은 2012년 1월에 밝혀졌고, 2013년 9월에 확인 되었다.[3][4]일본인 스도쿠 열광자가 많이 찾아냈다.[5][6]

규칙[편집]

기본 규칙[편집]

  • 아홉 3×3 칸에 숫자가 1부터 9까지 하나씩만 들어가야 한다.
  • 아홉 가로줄에 숫자가 1부터 9까지 하나씩만 들어가야 한다.
  • 아홉 세로줄에 숫자가 1부터 9까지 하나씩만 들어가야 한다.

심화 규칙[편집]

  • 숫자의 위치 (숫자와 상관 없이 들어간 위치) 가 좌우 대칭을 이루어야 한다.
  • 숫자가 30개 이하여야 한다.

스도쿠의 풀이법[편집]

1칸/가로줄/세로줄/3x3 칸에 들어갈 숫자 맞추기 등 여러가지 방법이 있다. 멘사에서 개발한 전문가용 방법 등도 있다. 방법이 상당히 많으므로 차라리 자신만의 방법을 만드는 것도 좋다.

스도쿠의 응용[편집]

직소 스도쿠[편집]

3X3 모양 스도쿠가 아닌 직소 모양으로 이루어진 스도쿠로, 규칙은 원래 스도쿠와 거의 같으나, 직소 모양 속에도 1에서 9까지의 숫자를 한 번씩만 쓸 수 있다는 것이 다르다.

대각선 스도쿠[편집]

스도쿠의 X자 모양의 대각선 속에서도 1에서 9까지의 숫자를 한 번씩만 사용할 수 있다.

부등호 스도쿠[편집]

이는 주어지는 숫자가 없는 대신 부등호에 맞게(예:1<2<3<4<5<6<7<8<9) 숫자를 채우는것.

점보 스도쿠[편집]

4X4 모양 네모칸에 1에서 16까지의 숫자가 들어가는 대형 스도쿠다. 푸는 방법은 일반 스도쿠와 동일하다.

각주[편집]

  1. 즉 '숫자들이 겹치지 말아야 한다'는 뜻의 일본어 신조어인 이 게임은 일본에서는 Number Place를 줄인 남프레(ナンプレ)라고도 한다.
  2. Jarvis, Frazer (2006년 7월 31일). “Sudoku enumeration problems”. 《Frazer Jarvis's home page》. 2006년 9월 16일에 확인함. 
  3. G. McGuire, B. Tugemann, G. Civario. "There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem". Arxiv.org.
  4. H.H. Lin, I-C. Wu. "No 16-clue Sudoku puzzles by sudoku@vtaiwan project" Archived 2014년 2월 14일 - 웨이백 머신, September, 2013.
  5. Royle, Gordon. “Minimum Sudoku”. 2012년 2월 28일에 확인함. 
  6. プログラミングパズルに関心のある人は雑談しましょう. 《プログラミングパズル雑談コーナー / Programming Puzzle Idle Talk Corner》 (일본어). 2006년 9월 16일에 확인함. 

외부 링크[편집]