스도쿠(Sudoku)또는 넘버 플레이스(Number Place)는 9X9 크기의 모눈종이 전체의 각 가로줄과 세로줄, 그리고 9X9 크기의 모눈종이를 나누는 9개의 3X3 구간을 각각 1에서 9까지의 숫자를 한 번씩만 사용하여 채워넣어 결과적으로 모눈종이 전체에 1에서 9까지의 숫자를 완전히 채워넣는 퍼즐게임이다. 각 모눈종이의 칸 하나마다 숫자를 하나씩 채울 수 있으며, 맨 처음 스도쿠 문제가 주어질 때 모눈종이의 일부는 숫자가 기입되어있다.
유래
1979년에 뉴욕의 퍼즐 잡지 회사인 '델 퍼즐 잡지'(Dell Puzzle magazine)가 '넘버 플레이스'(Number Place)라는 퍼즐을 배포하기 시작하였다. 은퇴한 건축가 하워드 간즈(Howard Garns)가 넘버 플레이스를 최초로 개발했다는 증언이 있지만,[1] 넘버 플레이스를 최초로 개발한 인물은 정확히 알려지지 않았다.[2] 1984년에 이 퍼즐이 '숫자는 반드시 하나씩만 있어야 한다.'라는 제목으로 번역된 후 일본에 전해져 인기를 끌었고, 이 퍼즐을 수입한 잡지사 '니코리'(Nikoli)는 제목을 축약해 '스도쿠'[3]라는 이름을 만들었다. 이후 1986년에 '니코리'는 넘버 플레이스에 맨 처음 주어지는 숫자의 최대 개수를 32개로 제한하고 주어진 숫자가 회전대칭이 되도록 배열한다는 두 개의 규칙을 추가한다.[4] 이후 스도쿠는 주로 일본에서 인기를 끌었지만, 1997년에 뉴질랜드인 웨인 굴드(Wayne Gould)가 도쿄에서 스도쿠를 접한 후 스도쿠 문제를 생성하는 프로그램을 개발한 후 이를 이용하여 2004년 11월 15일부터 런던의 '타임즈' 신문에 스도쿠 퍼즐을 실으면서 스도쿠는 세계적인 인기를 끌기 시작한다.[5]
푸는 방법
사람
컴퓨터
가장 기초적인 방법으로 백트래킹을 이용해서 조건에 맞는 배열을 얻을 때까지 숫자를 빈 칸에 일일이 다 대입해서 푸는 방법이 있다.