Nクイーン問題のアルゴリズムについて

Nクイーン問題のアルゴリズムについて

http://www.itmedia.co.jp/news/articles/0410/06/n …

↑このニュースにあるようなNクイーン問題の総数を求めるアルゴリズムは、どんな手法を使っているんでしょうか。
調べたところ、組み合わせ問題には「バックトラック法」が有効と出てきたのですが、世界記録を樹立したプログラムもそれを用いているんでしょうか。

ちなみにプログラムは以下のサイトからゲット出来ます。
http://www.arch.cs.titech.ac.jp/~kise/nq/index.htm


私にはさっぱりなので、どなたかわかる方ご教授ください。

No.1 ベストアンサー 回答者： rabbit_cat 回答日時： 2007/11/04 02:54

基本的には、こういう組み合わせの問題を真面目に（漏れなく）解こうとしたら、バックトラックでやるか、。

もしくは、線形計画法（あるいは整数計画法）の問題に変形して解くか、まあ大きく分ければ２通りの方法しかないです。
バックトラックの場合は、いかにうまく枝狩りを行うかが非常に重要で、そのための方法がいくつも提案されています。
そういう意味では、単にバックトラックというだけでは、ものすごく広い概念で、そのプログラム独自の工夫というか優れている点を述べるには不十分です。

この回答へのお礼

バックトラックにも様ざまな手法があるんですね。
ためになりました。
ありがとうございます。

お礼日時：2007/11/09 00:05