最小問題　ー　究極のナンプレ問題

□探索空間の大きさ

この問題の難しさを知っていただくために、一番簡単な以下のようなアプローチをとった場合どうなるかを試算してみることにします。

「すべての（Ｎ−１）の作図問題を作成して、その解があるかどうかを調べる」

仮に、Ｎ＝１９を想定すると、１８個の枠の作図問題をすべて解く事になります。
９Ｘ９＝８１個のマスから１８個の枠を選ぶ組合わせの数は、

81Ｃ18 ≒ ４．５ｘ１０の１７乗 通り

作図問題を１問解く時間を１秒（本当はこんな時間で済むとは思えないが）とすると、４．５ｘ１０の１７乗秒という想像を絶する時間がかかることになります。対称性を考慮すると少しは組合わせを減らすことは可能ですが、全体からみると焼け石に水です。（ちなみに、１年＝３．１５３６ｘ１０の７乗秒です）

果たして、リーズナブルな時間でこの問題を解くアルゴリズムは見つかるのだろうか？
（１年前は、ここで素直にあきらめたけど、こんどは少し悪あがきをしてみよう）