情報処理学会 第80回全国大会講演要旨

数独は世界的に有名なパズルで、9×9のマスに1~9の数字を、各行各列および3x3の小ブロックに各数字が一度ずつ出現するように埋めるパズルである。
　現在、世界でトップクラスの数独ソルバーは、数独の問題を直接的に解くのではなく、数独の問題をexact coverの問題とみなして、KnuthのAlgorithmXを用いて解くものが主流である。上記の方法は、選択肢の少ないものを優先に探索する、総当たり探索の一種である。
　本研究では、数独ソルバーのさらなる高速化を目的とし、数独エントロピーを最小化するものから探索する手法を提案するとともに、数独エントロピーの効率的な近似計算法を示す。通常の9×9の数独で1.3倍、16×16の巨大数独で6.6倍の性能向上をみた。