[nikomat:22425] Re: 返信:[Game]ana

[Koji YOSHIDA <yd@nikongw.nikon.co.jp>]

よしだっす。

In message <199809030522.OAA10446@nikongw.nikon.co.jp>
   "[nikomat:22422] Re: 返信:[Game]ana"
   ""N. Magome" <magome@nikongw.nikon.co.jp>" wrote:
 > この手の問題で、解の存在性や唯一性はどうやってわかるんでしょうかね。

兄じゃのプログラムのように、全部の「場合」を確かめる
という greedy な方法 (= Brute な方法) の他は、（きっ
と人間が頭の中でやるであろう）複数の制約条件から、無
矛盾なものを見つける方法 が あります。

前者は、生成検査法（GAもこれ）、後者は 制約の大きい文字
から順に（線形計画法的に）深さ優先探索を行い、矛盾（制約
違反）が生じたら バックトラックをかけるようにし、全部の
場合をやれば 良いと思います。

後者だと、たとえば N=9 では 明らかに解が無いことが分かった
時点（N=9では、他の制約を*必ず*違反することが分かった時点）
で、N=9 を使う 未探索の解が残っていても、それを探索すること
は無いでしょうから、効率は良いです。

＃ たとえば、Ｆ＞１ なら、明らかに Ｎ＜４ でないと、積は
＃ ６桁になります、制約違反になりますよね。

-----
 吉田幸司  (株)ニコン  zip.140-8601  <yd@nikongw.nikon.co.jp>  
         精機事業本部 半露３-10Ｇ ｜ 技術開発本部 技開２-２Ｇ
  voice: 03-3773-2846             ｜ 03-3773-1111 (ex.2772)
  fax  : 03-3775-9042             ｜ 03-3773-1167