最少個数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/12 13:38 UTC 版)
数独の初期配置の数字の最少個数は、17個である。2012年1月6日、アイルランドの数学者 Gary McGuire は「数独においてヒントが16個以下のものは解法を持ちえない」ということを証明した。証明にあたっては「ヒッティング・セット・アルゴリズム」を用いて単純化し、2年間で700万CPU時間をかけ、答えにたどり着いた。以前は、問題として成立する初期配置の数字の最少個数は結論が出ていなかったが、点対称の問題では18個（初出・パズル通信ニコリ31号、1990年）、線対称（対角線）・非対称のものでは17個（後者の初出・パズラー187号、1997年）のものが確認されていた。また、どの初期配置の数字もそれが無かったら唯一解でなくなる問題の初期配置の数字の最多個数は、今のところ35個のものが確認されている。 なお、複数の解が存在する初期配置の数字の最多個数は77個である。
※この「最少個数」の解説は、「数独」の解説の一部です。
「最少個数」を含む「数独」の記事については、「数独」の概要を参照ください。
ウィキペディア小見出し辞書の「最少個数」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 最少個数のページへのリンク
