스도쿠

섬네일|세로 칸(보라색)과 가로 칸(하늘색), 3×3 격자(연두색) 안 1~9까지의 숫자가 겹치지 않아야 한다. (정답)
섬네일|킬러 스도쿠 (정답)
섬네일|노노미노 또는 직소 스도쿠 (정답)
섬네일|워도쿠 퍼즐 (정답)

스도쿠(, ) 또는 넘버 플레이스()는 숫자 퍼즐로, 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐이다. 숫자넣기로도 불린다. “숫자는 한 번씩만 쓸 수 있다”()즉 '숫자들이 겹치지 말아야 한다'는 뜻의 일본어 신조어인 이 게임은 일본에서는 Number Place를 줄인 남프레()라고도 한다.를 줄인 말로 2005년 전 세계적으로 이 말과 함께 퍼즐이 퍼져나갔다. 퍼즐을 푸는 방법은 아홉 가로줄, 세로줄, 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)가 출판한 잡지 《퍼즐 통신 니코리》()일본의 사업가인 가지 마키(鍜治真起, 1951년 ~ 2021년 8월 10일)이었으며, 도서출판 (주)니코리의 창시자다.에 '스도쿠'라는 이름을 붙여 수록하면서 대중에게 보급되기 시작하여 2005년 무렵에 이르러 온 세계로 퍼져 나갔다.

 스도쿠의 수학 
 가능한 모든 경우의 값을 구하였는데, 그 수는 6670903752021072936960 (66해 7090경 3752조 210억 7293만 6960) 개나 된다.
 스도쿠 중에서는 풀리지 않는 문제도 있고, 답이 2개인 문제도 있다. 그래서 답이 1개인 문제를 만드는 것이 원칙이다.
 스도쿠 문제에서 유일한 풀이가 존재하는 문제의 숫자 개수의 최솟값은 17이다. 17개의 경우, 49000개가 넘는 스도쿠 문제가 알려져 있다. 증명은 2012년 1월에 밝혀졌고, 2013년 9월에 확인되었다.G. McGuire, B. Tugemann, G. Civario. "There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem". Arxiv.org.H.H. Lin, I-C. Wu. "No 16-clue Sudoku puzzles by sudoku@vtaiwan project" , September, 2013.일본인 스도쿠 열광자가 많이 찾아냈다.

 규칙 
 기본 규칙 
 아홉 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까지의 숫자가 들어가는 대형 스도쿠다. 푸는 방법은 일반 스도쿠와 동일하다.

 같이 보기 
 제약 충족 문제
 논리 퍼즐
 노노그램
 가쿠로

 각주 

 외부 링크 

 네이버 캐스트 - 스도쿠의 수학은?

분류:퍼즐
분류:NP-완전 문제
분류:일본의 발명품