数独の難易度はどう測る？

パズルの難易度は、推測なしで解くのに必要な最も難しい論理テクニック一つで定義されます。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 の仕組み や 最も難しい数独パズル をご覧ください。