数独の初期ヒント最小個数は「17」、それ未満では解けないと数学者が結論∴GIGAZINE
これまでに登場したパズルの中で、ヒントが最小だったのは17個で、16個以下のものは作れないのではないかと言われていました。これを証明するには16個のヒントが与えられた数独を解くという方法がありますが、コンピューターで計算しても相当な時間が掛かります。そのため、McGuireさんは問題を「hitting-set algorithm」を用いて単純化。2年間で700万CPU時間をかけて挑戦し、答えにたどり着きました。
McGuireさんは、今回の解法が数独だけではなく、遺伝子配列解明技術の分析や、セルラーネットワーク、その他の研究者による分析などに有用に用いられるのではないかと期待しています。
700万CPU時間ですか。かなり時間がかかったようですが、一体何パターンの問題を解いたのかなあ…
