스도쿠

스도쿠 규칙

스도쿠(数独, Sudoku)는 9×9 격자의 빈칸에 1부터 9까지의 숫자를 채워, 모든 가로줄(행)과 세로줄(열), 굵은 선으로 나뉜 3×3 박스 아홉 개에 1~9가 한 번씩만 들어가게 만드는 1인용 숫자 퍼즐입니다. 처음부터 적혀 있는 숫자(단서)를 실마리로 나머지 칸을 논리로 채웁니다. 더하기나 곱하기 같은 계산은 필요 없고 숫자는 서로 다른 기호일 뿐이어서, 1~9 대신 글자나 색을 써도 같은 퍼즐이 됩니다. 넘버 플레이스(줄여서 넘플)라고도 부릅니다.

1. 한 행(가로줄)에는 1~9가 한 번씩 들어갑니다.
2. 한 열(세로줄)에도 1~9가 한 번씩 들어갑니다.
3. 굵은 선으로 나뉜 3×3 박스에도 1~9가 한 번씩 들어갑니다.
4. 처음부터 있는 숫자는 바꿀 수 없습니다. 제대로 만든 퍼즐은 답이 하나뿐입니다.

이 글과 게임의 힌트에서는 행을 위에서부터 1~9행, 열을 왼쪽부터 1~9열, 박스를 왼쪽 위부터 글 읽는 순서로 1~9번 박스라고 부릅니다. 같은 행·열·박스에 있는 칸끼리는 서로 본다고 하며, 한 칸이 보는 칸은 20칸입니다. 어떤 칸에 들어갈 수 있는 숫자, 곧 그 칸이 보는 20칸에 아직 없는 숫자를 그 칸의 후보라고 합니다.

이 게임 하는 법

1. 위에서 난이도를 고릅니다. 쉬움·보통·어려움·매우 어려움 가운데 하나를 누르거나 새 퍼즐을 누를 때마다 새 퍼즐이 나옵니다. 푸는 중인 판이 있으면 버릴지 한 번 더 묻습니다.
2. 칸을 누르고 판 아래 숫자 패드로 숫자를 넣습니다. PC에서는 숫자 키 1~9로 넣고, 방향키로 칸을 옮기고, Backspace·Delete로 지웁니다. 숫자 패드의 작은 숫자는 그 숫자를 앞으로 몇 개 더 넣어야 하는지입니다.
3. 후보를 적어 두려면 메모를 켭니다(N 키). 메모를 끈 채 Shift를 누르고 숫자를 눌러도 메모가 됩니다. 칸에 숫자를 넣으면 같은 행·열·박스의 메모에서 그 숫자가 저절로 지워집니다.
4. 칸을 고르면 그 칸의 행·열·박스가 옅은 회색으로, 같은 숫자가 든 칸과 메모가 노랗게 표시됩니다. 같은 행·열·박스에 같은 숫자가 겹치면 두 칸이 모두 빨갛게 바뀝니다.
5. 81칸이 모두 정답과 같아지면 완성입니다. 완성 화면에는 걸린 시간과 이 퍼즐을 푸는 데 쓰인 기법이 나옵니다.

• 되돌리기(Z 또는 Ctrl+Z)는 숫자 넣기·메모·지우기를 한 번씩 되돌립니다. 숫자를 넣을 때 저절로 지워진 메모도 함께 되살아납니다. 판 비우기도 되돌릴 수 있습니다.
• 힌트는 다음에 확실히 채울 수 있는 칸을 초록으로 표시하고, 그 이유를 기법 이름과 함께 한두 문장으로 알려 줍니다. 싱글이 바로 보이지 않으면 먼저 필요한 후보 지우기를 순서대로 보여 주고, 정답과 다른 숫자가 있으면 그 칸부터 알려 줍니다. 힌트는 사용자의 메모가 아니라 판에 놓인 숫자로 후보를 다시 계산해 찾습니다.
• 실수 확인을 켜면 규칙에는 어긋나지 않아도 정답과 다른 숫자를 빨갛게 보여 줍니다. 기본은 꺼져 있습니다.
• 시간은 퍼즐이 나타난 순간부터 재고, 다른 탭으로 옮기거나 화면을 끄면 멈춥니다. 난이도별 최고 기록은 힌트와 실수 확인을 쓰지 않고 완성한 판만 남깁니다.
• 푸는 중인 판은 이 브라우저에 자동으로 저장되어, 페이지를 닫았다가 다시 열면 이어서 풀 수 있습니다. 퍼즐 번호를 적어 두면 난이도와 번호로 같은 퍼즐을 다시 열 수 있습니다.
• 인쇄를 누르면 지금 퍼즐의 문제만 A4 세로 한 장에 크게 인쇄됩니다. 답지도 인쇄를 켜면 둘째 쪽에 답이 나옵니다. 인쇄 창에서 PDF로 저장할 수도 있습니다.

풀이 기법

스도쿠 풀이는 "이 칸에는 이 숫자가 들어간다"(놓기)와 "이 칸에는 이 숫자가 못 들어간다"(후보 지우기)를 번갈아 찾는 일입니다. 아래 그림에서 초록 칸은 찾은 칸, 노란 칸은 근거가 되는 칸, 회색은 따지는 줄이나 박스이고, 작은 숫자는 후보, 빨간 취소선은 지우는 후보입니다. 그림은 기법의 모양만 보여 주려고 나머지 칸을 비워 둔 도식입니다.

히든 싱글과 네이키드 싱글

히든 싱글(hidden single)은 한 박스나 줄에서 어떤 숫자가 들어갈 수 있는 칸이 하나뿐인 경우입니다. 다른 칸에도 후보가 여럿 있어 겉으로는 "숨어" 있지만, 그 숫자 하나만 놓고 보면 자리가 정해집니다. 네이키드 싱글(naked single)은 한 칸이 보는 20칸에 1~9 가운데 여덟 개가 이미 있어 후보가 하나만 남은 경우입니다. 줄이나 박스에 빈칸이 하나만 남은 마지막 한 칸은 둘 모두에 해당하는 가장 쉬운 경우입니다. 쉬움 퍼즐은 이 세 가지만으로 끝까지 풀립니다.

히든 싱글은 한 숫자를 정해 판 전체에서 그 숫자가 있는 줄을 가로세로로 그어 보면 잘 보입니다. 왼쪽 그림처럼 네 개의 5가 1번 박스의 2·3행과 2·3열을 막으면, 박스에 5가 들어갈 자리는 1행 1열 하나만 남습니다. 이렇게 숫자별로 줄을 그어 보는 방법을 크로스해칭(cross-hatching)이라고도 합니다.

포인팅과 박스-라인 감소

박스와 줄이 겹치는 세 칸을 이용하는 기법입니다. 포인팅(pointing)은 한 박스에서 어떤 숫자의 후보가 모두 한 줄 위에 있을 때입니다. 그 숫자는 박스 안의 그 줄 어딘가에 들어가므로, 같은 줄의 박스 밖 칸에서는 그 숫자를 지울 수 있습니다. 반대로 박스-라인 감소(box/line reduction, 클레이밍)는 한 줄에서 어떤 숫자의 후보가 모두 한 박스 안에 있을 때, 그 박스의 나머지 칸에서 그 숫자를 지웁니다. 둘을 묶어 교차 기법(locked candidates)이라고 부르며, 보통 난이도에서 가장 자주 쓰입니다.

네이키드 페어와 히든 페어

한 줄이나 박스에서 두 칸의 후보가 똑같이 두 숫자뿐이면(네이키드 페어), 두 숫자는 그 두 칸이 나눠 가지므로 같은 줄·박스의 다른 칸에서 두 숫자를 지울 수 있습니다. 세 칸이 세 숫자를 나눠 가지면 트리플, 네 칸이면 쿼드입니다. 거꾸로 두 숫자가 들어갈 수 있는 칸이 같은 두 칸뿐이면(히든 페어), 그 두 칸은 두 숫자로 채워지므로 두 칸의 다른 후보를 모두 지웁니다.

X-윙과 스워드피시

한 숫자만 따로 보는 기법입니다. 두 행에서 어떤 숫자가 들어갈 수 있는 칸이 모두 같은 두 열에 있으면, 두 행의 그 숫자는 두 열을 하나씩 차지합니다. 그러니 그 두 열의 다른 칸에는 그 숫자가 들어갈 수 없습니다. 네 칸이 X자 모양의 직사각형을 이루어 X-윙(X-wing)이라고 하며, 행과 열을 바꿔도 같습니다. 세 행·세 열로 넓히면 스워드피시(swordfish), 네 행·네 열이면 젤리피시(jellyfish)입니다.

XY-윙과 XYZ-윙

후보가 두 개뿐인 칸 세 개로 만드는 기법입니다. 가운데 칸(축)의 후보가 x·y이고, 축이 보는 두 칸(집게)의 후보가 각각 x·z, y·z라고 합시다. 축이 x면 첫째 집게가 z, 축이 y면 둘째 집게가 z가 되므로, 어느 쪽이든 두 집게 가운데 한 칸은 z입니다. 그래서 두 집게를 모두 보는 칸에서는 z를 지울 수 있습니다. 이것이 XY-윙(XY-wing, Y-윙)이고, 축의 후보가 x·y·z 세 개인 경우는 XYZ-윙으로, 이때는 축과 두 집게를 모두 보는 칸에서만 z를 지웁니다.

강한 연결을 잇는 기법

어떤 줄이나 박스에서 한 숫자가 들어갈 수 있는 칸이 딱 두 칸이면, 둘 가운데 정확히 한 칸에 그 숫자가 들어갑니다. 이 두 칸의 관계를 강한 연결(strong link)이라고 합니다. 매우 어려움 퍼즐에는 이 연결을 이어 가는 기법이 필요합니다.

• 스카이스크래퍼·투스트링 카이트·터봇 피시: 강한 연결 두 개의 한쪽 끝끼리 서로 보면, 둘 다 그 숫자일 수는 없으므로 나머지 두 끝 가운데 적어도 한 칸은 그 숫자입니다. 두 끝을 모두 보는 칸에서 그 숫자를 지웁니다. 두 연결이 모두 행(또는 모두 열)이고 같은 열(행)에서 이어지면 스카이스크래퍼, 행 하나와 열 하나가 한 박스에서 이어지면 투스트링 카이트, 그 밖의 모양은 터봇 피시라고 부릅니다.
• W-윙: 서로 보지 않는 두 칸의 후보가 똑같이 x·y이고, x의 강한 연결 한 쌍이 두 칸을 하나씩 보면, 두 칸이 모두 x일 수는 없습니다. 따라서 둘 중 한 칸은 y이고, 두 칸을 모두 보는 칸에서 y를 지웁니다.
• 단순 컬러링: 한 숫자의 강한 연결을 모두 이어 칸을 두 색으로 번갈아 칠하면, 둘 가운데 한 색의 칸들이 모두 그 숫자입니다. 같은 색 두 칸이 서로 보면 그 색은 틀린 쪽이고, 두 색의 칸을 모두 보는 칸에는 그 숫자가 들어갈 수 없습니다.

난이도 기준

이 게임은 퍼즐을 만든 뒤 컴퓨터가 가장 쉬운 기법부터 차례로 써서 직접 풀어 봅니다. 싱글을 먼저 찾고, 싱글이 없을 때만 다음 단계 기법을 찾아 후보를 지우는 식입니다. 끝까지 푸는 데 쓴 가장 어려운 기법이 속한 단계가 그 퍼즐의 난이도입니다. 한 단계 아래 기법만으로는 풀리지 않는 퍼즐만 그 난이도로 내놓으므로, 예를 들어 어려움 퍼즐에는 X-윙이나 XY-윙 같은 어려움 단계 기법이 적어도 한 번 필요합니다.

"+"는 윗단계 기법에 더해 쓰인다는 뜻입니다. 단서 수는 이 게임이 난이도마다 퍼즐 300개를 만들어 센 값입니다.

표에서 보듯 보통·어려움·매우 어려움은 단서 수가 거의 같습니다. 단서가 적다고 어려운 것이 아니라, 단서가 어디에 어떻게 놓였는지에 따라 필요한 기법이 달라지기 때문입니다. 같은 300개에서 가장 자주 쓰인 기법은 보통이 포인팅(93%), 어려움이 XY-윙(86%)과 X-윙(33%), 매우 어려움이 스카이스크래퍼(55%)와 투스트링 카이트(43%)였습니다. 쿼드와 젤리피시처럼 표에 있어도 거의 나오지 않는 기법도 있습니다.

이 기법들로도 풀리지 않는 퍼즐, 예컨대 더 긴 체인이나 "이 숫자를 넣으면 모순"을 여러 단계 따라가는 추론이 필요한 퍼즐은 만들지 않습니다. 2012년 핀란드의 수학자 아르토 인칼라가 "세상에서 가장 어려운 스도쿠"로 소개해 알려진 퍼즐도 이 게임의 풀이기로는 끝까지 풀리지 않는 쪽에 속합니다.

답이 하나뿐인 퍼즐 만들기

단서만 보고 답이 둘 이상 나오는 퍼즐은 어느 순간 두 숫자 가운데 하나를 찍어야 해서 논리 퍼즐로서 실격입니다. 그래서 이 게임은 퍼즐을 다음처럼 만듭니다.

1. 숫자를 무작위 순서로 넣어 가며 되돌리는 방식(백트래킹)으로 규칙에 맞는 완성 판을 하나 만듭니다.
2. 판의 가운데를 중심으로 180° 돌렸을 때 겹치는 두 칸을 한 쌍으로, 무작위 순서로 단서를 지워 봅니다. 지울 때마다 가능한 답을 끝까지 세어 답이 하나인지, 목표 난이도까지의 기법만으로 끝까지 풀리는지 확인하고, 아니면 그 두 칸을 되살립니다. 쉬움은 단서를 36개 아래로는 지우지 않습니다.
3. 더 지울 수 있는 칸이 없으면 다시 풀어 보고, 가장 어려운 기법이 정확히 목표 단계일 때만 내놓습니다. 아니면 새 완성 판으로 처음부터 다시 합니다.

그래서 모든 퍼즐은 답이 하나이고, 표의 기법만으로 찍지 않고 풀립니다. 지뢰가 무작위로 놓이는 지뢰찾기는 두 칸 가운데 하나를 찍어야 하는 판이 생길 수 있지만, 이 스도쿠에서는 그런 판이 나오지 않습니다. 단서를 점대칭으로 놓는 것은 스도쿠라는 이름을 붙인 일본 니코리가 1986년에 정한 규칙으로, 지금도 많은 퍼즐이 따르는 관습입니다. 퍼즐 만들기와 풀어 보기는 모두 브라우저 안에서 이루어지고, 보통 1초도 걸리지 않습니다.

퍼즐 번호(1~999999)는 퍼즐을 만드는 데 쓴 난수의 씨앗입니다. 난이도와 번호가 같으면 언제나 같은 퍼즐이 나오므로, 번호를 알려 주면 다른 사람과 같은 퍼즐을 풀어 볼 수 있습니다. 사람이 손으로 만든 퍼즐처럼 첫 수를 의도해 설계하지는 않으므로, 모양이 아름다운 퍼즐보다 기법을 연습하기 좋은 퍼즐에 가깝습니다.

푸는 요령

• 많이 나온 숫자부터: 판에 이미 일고여덟 번 나온 숫자는 남은 자리가 적어 히든 싱글이 잘 보입니다. 숫자 패드의 남은 개수가 작은 숫자부터 훑어보세요.
• 박스 단위로 보기: 한 숫자를 정하고 박스 아홉 개를 차례로 보며 그 숫자가 들어갈 자리가 하나뿐인 박스를 찾습니다. 줄보다 박스에서 히든 싱글이 먼저 보이는 경우가 많습니다.
• 빈칸이 적은 줄 채우기: 빈칸이 두세 개 남은 줄이나 박스는 빠진 숫자가 몇 개뿐이어서 금방 정해집니다.
• 막히면 메모: 싱글이 더 보이지 않으면 빈칸에 후보를 적습니다. 후보가 두 개뿐인 칸(쌍)을 찾으면 페어, X-윙, XY-윙 같은 기법의 실마리가 됩니다.
• 찍지 않기: 숫자를 넣어 보고 틀리면 되돌리는 식으로 풀면, 틀린 숫자 위에 쌓은 칸까지 모두 고쳐야 합니다. 이 게임의 퍼즐은 모두 논리로 풀리므로 확실한 칸만 채우는 편이 결국 빠릅니다.

줄마다 주어진 조건으로 칸을 칠해 그림을 완성하는 노노그램도 스도쿠처럼 답이 하나뿐인 논리 퍼즐이어서, 한 줄씩 가능한 경우를 따지는 연습을 함께 하기 좋습니다.

역사와 이름

• 영어 위키백과에 따르면 19세기 말 프랑스 신문에 비슷한 숫자 퍼즐이 실렸습니다. 파리 일간지 르 시에클(Le Siècle)이 1892년 11월 19일에 3×3 칸이 있는 9×9 마방진 퍼즐을 실었고, 라 프랑스(La France)가 1895년 7월 6일 이를 오늘날 스도쿠에 가까운 모양으로 다듬었습니다.
• 지금 형태의 스도쿠는 미국 인디애나주의 은퇴한 건축가이자 퍼즐 작가 하워드 간스(Howard Garns)가 만든 것으로 보이며, 1979년 미국 델 매거진(Dell Magazines)에 넘버 플레이스(Number Place)라는 이름으로 실렸습니다.
• 일본 퍼즐 회사 니코리(ニコリ)는 미국 잡지에서 이 퍼즐을 보고 1984년 자사 잡지에 「숫자는 독신에 한한다(数字は独身に限る)」라는 이름으로 소개했습니다. 이 긴 이름을 줄인 것이 스도쿠(数独)로, 스(数)는 숫자, 도쿠(独)는 하나뿐이라는 뜻입니다. 이름을 줄인 사람은 니코리를 세운 가지 마키(鍜治真起)입니다.
• 니코리에 따르면 처음에는 바로 인기를 끌지 못했고, 1986년 단서를 대칭으로 놓는다는 규칙을 정한 뒤 크게 유행했습니다. 스도쿠는 일본에서 니코리의 등록 상표여서 다른 일본 출판사는 넘버 플레이스(줄여서 난프레)라고 부릅니다.
• 뉴질랜드 출신 웨인 굴드(Wayne Gould)는 1997년 도쿄에서 이 퍼즐을 보고 6년에 걸쳐 퍼즐을 만들고 난이도를 매기는 프로그램을 개발했습니다. 그의 제안으로 영국 신문 더 타임스(The Times)가 2004년 11월 12일 "Su Doku"라는 이름으로 연재를 시작했고, 이후 세계 여러 신문으로 퍼졌습니다.

숫자로 보는 스도쿠

• 완성된 판의 수 6,670,903,752,021,072,936,960은 2005년 베르트람 펠겐하우어(Bertram Felgenhauer)와 프레이저 자비스(Frazer Jarvis)가 논문 「Enumerating possible Sudoku grids」에서 컴퓨터로 센 값입니다.
• 숫자를 서로 바꾸거나 판을 돌리고 뒤집는 등으로 서로 같아지는 판을 하나로 치면 5,472,730,538가지이며, 에드 러셀(Ed Russell)과 프레이저 자비스가 계산했습니다.
• 답이 하나뿐인 퍼즐에 필요한 단서는 최소 17개입니다. 게리 맥과이어(Gary McGuire)·바스티안 투게만(Bastian Tugemann)·질 시바리오(Gilles Civario)가 2012년 1월 "16단서 스도쿠는 없다"는 논문을 공개했고, 모든 경우를 컴퓨터로 확인한 이 결과는 2014년 학술지 Experimental Mathematics에 실렸습니다.
• 수학적으로 완성된 스도쿠 판은 각 행과 열에 기호가 한 번씩 들어가는 라틴 방진에 박스 조건을 더한 것입니다. n²×n² 크기로 일반화한 스도쿠에 답이 있는지 판정하는 문제는 NP-완전 문제로 알려져 있습니다.

자주 묻는 질문

규칙과 역사는 니코리 공식 사이트의 스도쿠 소개, 영어 위키백과 「Sudoku」·「Mathematics of Sudoku」, 나무위키 「스도쿠」를, 수치는 Felgenhauer·Jarvis(2005)와 McGuire·Tugemann·Civario(arXiv:1201.0749)를 참고했습니다(2026년 9월 확인). 난이도별 단서 수와 기법 비율은 이 게임의 생성기로 직접 센 값입니다. 퍼즐은 브라우저 안에서 만들어지며, 진행 중인 판과 기록은 이 브라우저에만 저장되고 서버로 전송되지 않습니다.