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

前へ 次へ
このQ&Aのポイント
  • Nクイーン問題のアルゴリズムについて調査した結果、バックトラック法が有効であることがわかりました。
  • 世界記録を樹立したプログラムもバックトラック法を使用しています。
  • Nクイーン問題のアルゴリズムに関する詳細な情報は以下のサイトで入手できます。
回答を見る
  • ベストアンサー

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

Nクイーン問題のアルゴリズムについて http://www.itmedia.co.jp/news/articles/0410/06/news079.html ↑このニュースにあるようなNクイーン問題の総数を求めるアルゴリズムは、どんな手法を使っているんでしょうか。 調べたところ、組み合わせ問題には「バックトラック法」が有効と出てきたのですが、世界記録を樹立したプログラムもそれを用いているんでしょうか。 ちなみにプログラムは以下のサイトからゲット出来ます。 http://www.arch.cs.titech.ac.jp/~kise/nq/index.htm 私にはさっぱりなので、どなたかわかる方ご教授ください。

質問者が選んだベストアンサー

  • ベストアンサー
  • rabbit_cat
  • ベストアンサー率40% (829/2062)
回答No.1

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

inaina5
質問者

お礼

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

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. その他（プログラミング・開発）

関連するQ&A

  • GA(遺伝的アルゴリズム)でNクイーン問題の解を求めるとき・・・

    GAでNクイーン問題の解を求めるとなると、各Nにおける解の総数がわかっていないと解けないのではないかと思います。 普通GAでNクイーン問題を解くと言ったら、複数ある解の内の一つ(クイーンの配置)を示せばいいんでしょうか。

  • アルゴリズム　フェルナンデスとは？

    こんにちは。 Nクイーン問題探索アルゴリズムは、 チェスのような基盤にクイーンを取られないように 何個配置できるかという問題だと思います。 同じようなものだと思うのですが、 アルゴリズム　フェルナンデス、Fernandes問題 もしくはフェルナンデスの法則や定理を聞いたことがありますか？ 知っていたら教えてください。 よろしくお願いします。 以上

  • Nクィーン問題のJAVAソースコード

    お世話になっております。 Nクィーン問題のJAVAプログラムソースを探しています。C言語では見つかるのですが、JAVAでは見つかりません。どこで見つけられるのかご存知の方がおられましたら教えて頂けるとうれしいです！ よろしくお願い致します。

  • N-Queen 問題

    　N-Queen問題を考えています。 　なかなかうまくいきません。 　どうやったら解けるか、アルゴリズムでも下の私が考えたプログラムでもいいんでアドバイスください。 （４×４の場合） #include<stdio.h> #define BYTESIZE 8 void printbits(unsigned i); struct data { int basho; unsigned l1,l2,tate,x; }; int main(void) { unsigned m,l,hojo=0; int kenchi,i,j,k; struct data a[5]; for(i=0;i<=3;++i) { l=1<<i; hojo|=hojo|l; } a[0].l1=0; a[0].l2=0; a[0].tate=0; for(kenchi=0;kenchi<=3;) { for(i=1;i<=4;) { a[i].x=0; for(j=a[i].x;j<=3 && ((~l)&hojo)==0;++j) { m=1<<j; a[i].l1=((a[i-1].l1)<<1)&hojo; a[i].l2=((a[i-1].l2)>>1)&hojo; a[i].tate=(a[i-1].tate)|m; l=(a[i].l1)|(a[i].l2)|(a[i].tate); a[i].x=j+1; } if((~l)&hojo) { a[i].basho=j; a[i].l1=(a[i].l1)|m; a[i].l2=(a[i].l2)|m; ++i; if(i==5) {for(k=1;k<=4;++k) printf("%d ",a [k].basho);printf("\n");} } if(j==3)--i; if(i==0) kenchi++; } } } void printbits(unsigned intval) { unsigned i; for(i=0;i<BYTESIZE*sizeof(unsigned);++i) printf("%d",(intval<<i&1<<BYTESIZE*sizeof(unsigned)-1)?1:0); putchar('\n'); } 　tateで駒があった列、l1で左にずらしたもの、l2で右にずらしたものを表しています（うまく説明出来なくすいません）。 参考URL：http://oshiete1.goo.ne.jp/kotaeru.php3?qid=330589 　

  • OKWeb利用規約における、投稿内容の著作権のOKWebへの帰属

    OKWebの利用規約には、このBBSへの投稿内容の著作権は、OKWebへ帰属するとあります そこで、パブリックドメインの著作物(著作権)や作品などを投稿した場合でも OKWebに著作権が移動してしまうのでしょうか また、コンピューターソフトウェアの質問に対してアルゴリズムを書いた場合 そのアルゴリズムの著作権がOKWebに移ってしまうと、そのアルゴリズムを利用するに当たり いわゆる著作権問題が発生してしまうのではないか、と思います 自分で考えた手法を広く自由に使ってほしいために 他の人が特許を取って使用を制限させないように、自分で著作権(特許)を保持したいという場合でも OKWebの質問の回答には、投稿することはできないと思います また、同様にプログラムコードそのままを投稿して質問や回答をすると それらの著作物をOKWebに無断で自由に使っても良いという明確な記載は見られなかったため OKWebに帰属した著作権は、OKWebに使用許可を得なければ、著作権法違反になる可能性があると思います 利用規約は利用者のみに関係しますが、著作権法は利用者でなくても守らなければならない法律ですので OKWebを利用しない人にも影響があるのではないか、と思います 過去の投稿に関して、著作権問題のニュースは聞いていませんが 今後、OKWebが著作権を主張しない、という保証は全くないと思います LZW圧縮アルゴリズム(GIF画像)が特許として認められているように アルゴリズムそのものにも著作権がありますし プログラムコードそのものは著作物です http://itmedia.okwave.jp/kotaeru.php3?q=1579437 http://itmedia.okwave.jp/kotaeru.php3?q=1362668 http://itmedia.okwave.jp/kotaeru.php3?q=633696 http://itmedia.okwave.jp/kotaeru.php3?q=159345 http://itmedia.okwave.jp/kotaeru.php3?q=157009

  • アルゴリズム・ネストループ方式って何？

    プログラムの性能改善の課題が出ているのですが、アルゴリズムとしてネストループ方式、もしくはその延長上のものを用いること、とあります。 図書館でアルゴリズム関係の本を見てみたのですがどこにもネストループに関して説明がなく、大変困っています。 プログラム自体は、ファイルを読み込んで、表示させるだけの簡単なものです。 簡単に抜き出すと、 for (i=0;; i++){ if ((st = read_a(fd_name, &name_buf, i)) <=0) break; for (j = 0;; j++){ if ((st =read_a (fd_home,&home_buf ,j)) <= 0) break; if (!strcmp(name_buf.a , home_buf.b)){ printf("%s =%s (%s)\n", name_buf.a, name_buf.c , home_buf.c); } } if (st <0) break; といったものです。 注意事項として、break文を入れる手法を使わないこととあります。 お願いします。ネストループって何でしょう？教えてください。

  • 数独をとくプログラム

    Ｃ初心者です。大学生です。 タイトルの通り、Ｃで数独を解くプログラムを考えています。 数独については http://www.nikoli.co.jp/puzzles/1/ をご参照ください。 で、数独にも難易度があり、初めからある程度数字が埋まっている（簡単な） 問題を解くプログラムは作ることが出来ました。 単純に、各マスの構造体Cellに対してsign[1],sign[2],,,,,sign[9]を定義し、 それが１なら可能性あり、０なら可能性なし、として （例えばsign2]==1,sign[5]==0ならそのマスは２になる可能性はあるが５になることはない） 丹念に各マスに対してそのマスが属するブロック、列、行を調べて最後まで１であるflagを探すようにしたのです。 しかし初めから埋まっている数字が少ないと（難しいと）そもそも回答が１通りでない、 などの理由から上記のアルゴリズムでは解くことが出来ません。 あきらかにどこかをあてずっぽに仮定する作業（バックトラック？） が必要になりそうです。 ・・・が、それをどうやって実現したらいいかで行き詰っています。 どうか知恵を貸してください。よろしくお願いいたします。。。

  • うるう年判定のアルゴリズム

    javaでうるう年判定のプログラムを作成しています。 プログラム自体はサーバにアップするときに実行結果が正しいかどうかテストされます。 仕様としては、 1.時間に関するAPIなどは一切使わずに完全に自作 2.入力される値はLong型の"秒"数(APIで提供されているのはミリ秒ですが) 3.60537895631062456L などの入力値に対して、年/月/日 (曜日) 時:分:秒 yday=元旦からの経過日数 を出力 最初は以下の関数を使用してループをかけていたのですが、仕様3の入力値に対して50秒近くかかってしまい、上手くいきませんでした。 public static int isLeap(int year){ if(year%4==0 && (year%100!=0 || year%400==0)) return 1; return 0; } 問題点はループ回数が多いことで、作る時点で分かってはいたのですが、ここまで遅くなるとは思っても見ませんでした。 これを使わない方法としては、一回だけうるう年(=n)を見つけ、その後は「(n+4)との比較+100で割り切れず400で割り切れる場合は別」という処理を行うことによって、処理時間を30秒付近にまで短縮することができたのですが、どうも10～15秒以内で終わらせなければテストにパスすることができないようです。 なんとか色々考えてはみたものの、上手いアルゴリズムは思いつきませんでした。 うるう年を処理するための"高速な"アルゴリズムはないのでしょうか。 お知恵を貸してください。よろしくお願いします。

    • ベストアンサー
    • Java
  • うるう年判定のアルゴリズム

    javaでうるう年判定のプログラムを作成しています。 プログラム自体はサーバにアップするときに実行結果が正しいかどうかテストされます。 仕様としては、 1.時間に関するAPIなどは一切使わずに完全に自作 2.入力される値はLong型の"秒"数(APIで提供されているのはミリ秒ですが) 3.60537895631062456(Long値) などの入力値に対して、年/月/日 (曜日) 時:分:秒 yday=元旦からの経過日数 を出力 最初は以下の関数を使用してループをかけていたのですが、仕様3の入力値に対して50秒近くかかってしまい、上手くいきませんでした。 public static int isLeap(int year){ if(year%4==0 && (year%100!=0 || year%400==0)) return 1; return 0; } 問題点はループ回数が多いことで、作る時点で分かってはいたのですが、ここまで遅くなるとは思っても見ませんでした。 これを使わない方法としては、一回だけうるう年(=n)を見つけ、その後は「(n+4)との比較+100で割り切れず400で割り切れる場合は別」という処理を行うことによって、処理時間を30秒付近にまで短縮することができたのですが、どうも10～15秒以内で終わらせなければテストにパスすることができないようです。 なんとか色々考えてはみたものの、上手いアルゴリズムは思いつきませんでした。 うるう年を処理するための"高速な"アルゴリズムはないのでしょうか。 お知恵を貸してください。よろしくお願いします。

  • 閉店詐欺　景品表示法

    閉店商法など、景品表示法に定める不当表示に該当するおそれがあるものを、 一方では、悪いニュースで、もう一方では良いニュースとなっている。 ーーー悪いニュース http://www.itmedia.co.jp/business/articles/1602/16/news130.html アディーレ法律事務所に措置命令　「今だけ」“期間限定”キャンペーン、実際にはほぼ常時 ーーー良いニュース http://www3.nhk.or.jp/news/html/20160220/k10010416301000.html 「店じまい」で３０年営業の靴販売店が閉店 大阪 この違いは何でしょうか？公平性を大きく欠くと思います。 この扱いは、大きな問題だと想います。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する