数独が持つことができる最小の手がかりの数は何ですか？

2012年、ダブリン大学ユニバーシティ・カレッジのGary McGuire、Bastian Tugemann、Gilles Civarioは、有効な16-clue Sudokuは存在しないという証明を発表しました。彼らの研究は主に計算によるものでした。可能な16-clueグリッドの全空間を探索し、一意の解を生成するものがないことを確認しました。この探索には約700万コア時間の計算が必要でした。

これ以前は、17が最小であると広く信じられており、何千もの17-clueパズルが実験的に見つかっていました。McGuireのチームは、16が不可能であるという最初の厳密な証明を提供しました。

17ヒントパズルは非常に疎らです - 81セル中17の与えられた数字で、64が空です。これらは解くのが最も難しいパズルの一つであり、通常高度なテクニックが必要です。有効な17ヒントパズルを見つけること自体に数十年の計算努力が必要でした。執筆時点で、49,000以上の本質的に異なる17ヒント数独パズルが知られています。

人間のソルバーを対象とした公開パズルは、22 clueを下回ることはめったにありません。ExpertおよびMaster難易度のパズルは通常22-27の与えられた数字を使用し、Easyパズルは36-45を使用します。17-clueの最小値は理論的な限界です。実際には、適切なテクニックと楽しい解決経路による解決可能性が、clueの数だけよりもはるかに重要です。