스도쿠 난이도는 어떻게 측정하나요?

퍼즐의 난이도는 추측 없이 풀어내는 데 필요한 가장 어려운 논리 기법 하나로 정의됩니다. Sudoku Explainer 같은 솔버는 고정된 기법 사다리 — 네이키드 싱글부터 포싱 체인까지 — 를 따라 퍼즐을 풀어 나가며, 써야 했던 가장 높은 단을 숫자, 곧 SE grade 로 보고합니다. 방법이 고정되어 있고 재현 가능하기 때문에 같은 퍼즐은 항상 같은 등급을 받고, 그래서 우리는 "쉬움"이나 "전문가" 같은 모호한 말 대신 모든 판을 이 방식으로 채점합니다.

꼭 그렇지는 않습니다. 유효한 스도쿠가 정확히 하나의 정답을 유지하면서 가질 수 있는 최소 단서 수는 17 입니다 — 전수 컴퓨터 탐색으로 증명됐어요(McGuire, Tugemann and Civario, 2012). 하지만 단서 개수는 난이도와 약하게만 연동됩니다: 단서 17개짜리 퍼즐이 순할 수도 있고, 30개짜리가 고급 체인을 요구할 수도 있어요. 중요한 건 빈칸의 수가 아니라 배치가 강제하는 기법입니다.

완전히 풀린 스도쿠 격자는 6,670,903,752,021,072,936,960 개 — 약 6.67 × 10²¹ 개 — 있으며(Felgenhauer and Jarvis, 2005), 대칭을 제거하면 본질적으로 서로 다른 5,472,730,538 개로 줄어듭니다. 실질적으로는 어떤 난이도든 한 번도 본 적 없는 새 퍼즐이 결코 바닥나지 않는다는 뜻이에요.

AI Escargot(Arto Inkala, 2006) 같은 유명한 "몬스터"는 한때 역대 가장 어려운 퍼즐로 홍보됐습니다. SE grade 는 이들을 평판이 아니라 객관적으로 비교하게 해줘요: 알려진 가장 어려운 퍼즐들은 SE grade 11 안팎과 그 이상에 있습니다.

몬스터 명단은 SE grade 가 작동하는 방식 이나 가장 어려운 스도쿠 퍼즐 을 보세요.