なぜ数独のヒントは「17個」より減らせないのか──スパコン700万時間の証明【数独/ナンプレ】
- 2026/07/13 22:09:15 投稿
- 再生数：15
- マイリスト数：0
数独のヒントは、17個より減らせません。 16個の数独が「存在しない」ことは、2012年、のべ700万CPU時間の総当たりで証明されました。 この動画では、その証明のアイデア(ヒッティングセット)と、 「唯一解」という数独の生命線を、盤面の実演で読み解きます。 理不尽は、設計で消せる。 ▼ 動画内で紹介した「16ヒントの数独」で実際に遊べます(解が一意に定まらない感覚を体験できます) https://puzzlebyrinth.com/puzzles/sudoku16 ■ 目次 0:00 17という最小 0:29 数独のルール(確認は3秒) 0:50 ただ一つの解 ── 唯一解という生命線 1:15 17ヒントは約4万9千問、16はゼロ 1:32 総当たりの規模 ── 6.67×10²¹ 2:05 賢い総当たり ── ヒッティングセット 2:58 結果はゼロ ── 16ヒントは存在しない 3:17 証明された最小「17」 3:36 「存在しない数独」で遊ぶ 3:53 結び ■ 一次資料(この動画の学術的な参考資料) ・G. McGuire, B. Tugemann, G. Civario, "There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration" arXiv:1201.0749(2012)/ Experimental Mathematics 23:2(2014) ※「のべ700万CPU時間」の出典 ・B. Felgenhauer, F. Jarvis, "Enumerating possible Sudoku grids"(2005) ※完成盤の総数 6,670,903,752,021,072,936,960 の出典 ・E. Russell, F. Jarvis, "Mathematics of Sudoku II"(2006) ※本質的に異なる盤 5,472,730,538 通りの出典 ・Gordon Royle, "Minimum Sudoku"(17ヒント問題のコレクション、約49,000問) 数値・年号は上記の一次資料に基づいています。誤りを見つけた場合はコメントで教えてください。確認のうえ、概要欄と固定コメントで訂正します。 ■ パズルラビリンスについて ゲームを、ゲームデザインの視点で読み解くチャンネルです。 姉妹サイトでは、オリジナルパズル(Tridem / CRYPTEM / Math?)を毎日1問、8言語で出題しています。 https://puzzlebyrinth.com