■数独アルゴリズム(その2)

 数独とは9×9のマスがあり,

[1]各行

[2]各列

[3]3×3のマス

のなかに1〜9の数字が1回ずつはいるパズルである.人間がパズルとして解くものは解が一つだけのものに限られているから,パズルが適正であるなら,数字の入れ方は1通りしかない.

 魔方陣の変形版ともいえるが,これを発明したのは日本人(鍛冶真起さん)で,いまや世界中の人々が数独を楽しんでいる.(私はまったくやったことはないが,周りにはたくさんのはまっている人がいる.)

 私は数学の師匠をもたないが,プログラムの師匠はいて,それが本永朝雄先生(横浜市)である.Google などで「数独プログラム」とか「数独アルゴリズム」で検索すると,本永先生の作られたプログラムがかなり上位でヒットする.もう何年も前のものであるが,いまでも日に10人くらいが見に来るらしい.

  URL :http://www.geocities.jp/motonaga_asao/

===================================

 本永先生に窺った話によると,

[1]大規模電気回路を解くことを研究テーマにしていた本永先生の友人が,人間が解くときに使用する解法をプログラムにしていたのであるが,1,000 ステップ以上のものになっていた.

[2]それを見て自分なら半分以下のステップで作れると言ったら,それなら作ってみろと煽られた.

[3]短いプログラムで作ることができたのはプログラミング・テクニックではなく,アルゴリズムの問題である.非数値解析の世界には決まった解法のない問題,例えば「八王妃の問題」とか「騎士の巡回」を解くのに使用する「バックトラック」がある.

[4]これを使用すると 500 ステップどころか 100 ステップほどで出来てしまった.しかも,複数の解を持つ問題でも,極端な例で全くの白紙の場合でも解を延々と出力することができる.

===================================

[雑感]数独の問題が適正ならば必ず解は一意である.プログラムのステップ数を短くしても,アルゴリズムが適正ならば,解けない問題が出てきたりはしないのである.

===================================

ところで、2012年、数独の答えが1通りに限られるためには最小限17個の数字が与えられなければならないことが証明されました。

17個より少なければ解けません。

===================================