エイトクイーンのプログラムを書くには？
エイトクイーンのプログラムの
書き方を教えてください
アルゴリズムは解っていらっしゃいますか？
「Nクイーン問題」で検索すると、たくさん出てきます。
出力方法によっても、少し変わってきます。
C言語がわかるのであれば、
「C言語による最新アルゴリズム事典」
に、Nクイーン問題のソースが載っています。
http://oku.edu.mie-u.ac.jp/~okumura/algo/
CからPascalへの置き換えは簡単ですよ。
中には難しい物もありますが、Nクイーン問題は単純ですから。
学校の課題で出されたのですが・・・・サッパリで。
その解とかはネットで見つけられたのですが
Delphiでエイトクイーンを動かすプログラム？がサッパリわからなくて混乱しているんです。
アルゴリズムの説明とかあるんですがどういうことなんでしょうか。
とりあえず、『Ｎクイーン問題』を調べてみます。
すみません・・・・・。ホントわからなくて泣きそうです。
あせっていては、何もならない
まずは、おちつけ
Nクイーン問題は、汎用的なクイーン問題のことです。
# NxNマスを使ったクイーン問題
N=8であれば、エイトクイーン問題です。
ルールは至って簡単で、クイーンの動ける範囲(横方向、縦方向、斜め方向)に、別のクイーンがいなければよいだけです。
時間があれば、ここでレクチャーできますが、解答をズバリだと良くないと思いますので・・・。
ヒントを１つ。
Form1に、
TStringGrid(名前はStringGrid1)を１つ張る。ColCount, RowCountは８。FixCols, FixRowsは0
Button1をはる。
Button2をはる。
Button1のOnClickイベントに、
procedure TForm1.Button1Click(Sender: TObject);
var
x, y: Integer;
begin
for x := 0 to 7 do
begin
for y := 0 to 7 do
begin
StringGrid1.Cells[x,y] := IntToStr(x+y);
end;
end;
end;
と記述。
Button2のOnClickイベントに、
procedure TForm1.Button2Click(Sender: TObject);
var
x, y: Integer;
begin
for x := 0 to 7 do
begin
for y := 0 to 7 do
begin
StringGrid1.Cells[x,y] := IntToStr(7 - x + y);
end;
end;
end;
と記述。
これらの動作を見ると、ちょっと光が見えるかも。
動作結果は、
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 11
5 6 7 8 9 10 11 12
6 7 8 9 10 11 12 13
7 8 9 10 11 12 13 14
と
7 6 5 4 3 2 1 0
8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2
10 9 8 7 6 5 4 3
11 10 9 8 7 6 5 4
12 11 10 9 8 7 6 5
13 12 11 10 9 8 7 6
14 13 12 11 10 9 8 7
になります。
斜めに連番が振られるので、クイーンの斜めに対して配列で存在の有無を持つことが簡単にできます。
がんばれ学生！
解答をズバリだとありがたいんですが・・・。
もうその先生の授業はまったく自己満足というかそういう感じでわからなくて。
なんとかやってみますが、解答もできればお願いします。
答えあわせしたいので・・・。できるか・・・・わかりませんけども。
まあ、アルゴリズムというのは、定石ですし。解答を見て勉強になるということもありますからね。
ただ、この程度はすぐ思いつくようにしておいたほうが良いです。
# プログラマ/SEなどを目指していないのであれば、単位さえ取れれば問題ないんですが^^;
そのままでは動きません。
変数の宣言位置や、関数の宣言位置はDelphiの構文に則って書いてください。
ここに書くのは主要部分のみです。
[変数宣言]
ans: Integer; // 解の何番目か。
Row: array[0..N-1] of Boolean;// 各行に置ける、クイーンの位置(0~7)。埋まっていたらTrue
Col: array[0..N-1] of Integer;// 各行に置ける、クイーンの位置(0~7)。位置が入る。
RU: array[0..2*N-2] of Boolean; // 右上から左下に向かう斜めの位置(0~15)。埋まっていたらTrue
LU: array[0..2*N-2] of Boolean; // 左上から右下に向かう斜めの位置(0~15)。埋まっていたらTrue
//関数宣言
procedure NQueen(i: integer);
procedure PutQueen;
変数の宣言と関数の宣言は、TForm1のメンバとして。
また、TStringGrid(名前はStringGrid1)と、TButton(名前はButton1)をFormに貼り付け、Button1のOnClickイベントを定義します。
関数の実装は以下の通り。
procedure TForm1.Button1Click(Sender: TObject);
var
i: integer;
begin
//初期化
for i := 0 to N - 1 do
begin
Row[i] := False;
end;
for i := 0 to 2 * N - 2 do
begin
RU[i] := False;
LU[i] := False;
end;
//検索
ans := 0;
NQueen(0);
end;
procedure TForm1.NQueen(i: integer);
var
j: integer;
begin
for j := 0 to N - 1 do
begin
// 置ける？
if (not Row[j])
and (not RU[i + j])
and (not LU[N - 1 - i + j]) then
begin
//置けるので置く
Col[i] := j;
if i < N - 1 then
begin
//まだ置き終わっていない
Row[j] := True;
RU[i + j] := True;
LU[N - 1 - i + j] := True;
NQueen(i + 1);
Row[j] := False;
RU[i + j] := False;
LU[N - 1 - i + j] := False;
end
else
begin
//置き終わった
PutQueen;
end;
end;
end;
end;
procedure TForm1.PutQueen;
var
i, j: integer;
begin
// printf("\n解 %d\n", ++solution);
for i := 0 to N - 1 do
begin
for j := 0 to N - 1 do
begin
if Col[i] = j then
begin
StringGrid1.Cells[i, j] := '○';
end
else
begin
StringGrid1.Cells[i, j] := ' ';
end;
end;
end;
inc(ans);
ShowMessage(Format('解%d', [ans]));
end;
うーなんとかがんばってみます・・・。
プログラマ目指してるどころか、ただの経済学部です。
上のはプログラム？はそのまま書いたんではダメなんですか？
TStringGridの張り方もわからなかったんですが何とかそれは貼れたんですが。というかそんなレベルです。
Delphiの構文とかもあんまりというか・・・
あと、もう本当に教えて教えてうざいと思いますが
「モンテカルロシュミレーションによって
円周率の近似値を求める」という課題も意味がわかりません。
クイーンよりずっと簡単だと言ってましたが。
なんかもうホンとすみません
経済学部ですか。経済学部でもこういう(パズル的な)プログラムって必要なんでしょうか^^;
そのまま書くだけではだめですね。
一時的に、
http://www.overs.jp/software/comps/NQueen.zip
においておきます。
Delphi7Proで作成したものです。
バージョン違うと開けないかも。
モンテカルロ法は単純ですよ。
簡単に言えば、
・１ｃｍ四方の四角に、ランダムな点を置き、それぞれの点の左下からの距離が、１ｃｍ以下の点の数を数える。
・全体の数に対する、１ｃｍ以下の点の数の割合
が、π/4になります。
# これはわかりますよね？
ついでに、これも作りました。
procedure TForm1.Button2Click(Sender: TObject);
const
N = 10000; // 試行回数
var
A: integer; // 1以下の回数
x, y: double;
i: integer;
da: double;
begin
Randomize;
A := 0;
for i := 0 to N - 1 do
begin
x := Random;
y := Random;
if (x*x+y*y) <= 1 then Inc(A);
end;
da := 4*A / N;
Memo1.Lines.Add(FloatToStr(da));
end;
経済にまったくかんけいないんですが
選択科目で取らないといけないんですよ・・・・・いじめです。
重ね重ねありがとうございますです。
今家なのでDelphiが使えないので学校に行ってやってみます。
ほんとうに手間をかけてすみません。
誰か『モンテカルロシュミレーションによっての円周率の近似値の求め方』と、『騎士の巡回問題』のソースを教えていただけないでしょうか？
ほんとうに何回やってもできないのでよろしくお願いします。
とりあえず、本題「エイトクイーンのプログラムを書くには？」とは関係無いので新たにスレッドたててください。
あと質問は一つずつの方が回答が付きやすいですよ。
さらに、少しでも挑戦したのであれば恥ずかしくてもソースを公開した方がレスが良いですよ。丸投げなら丸投げだと言った方がこれまた回答がつきやすいかと思います。
アドバイスありがとうございます。
友人たちとも協力したのですが、恥ずかしながら現在ほぼ丸投げ状態です。
おかげさまで、エイトクイーンプログラムは書けました！
ありがとうございます。本当に。
あと、最後のお願いなのですが
「（レポート用紙に）ＰＡＤによるエイトクイーンのアルゴリズムの説明。」
というものがあるんですがこれはどうすればいいんでしょうか。
具体的に何を書けばいんでしょうかわかりません。あいかわらず。
手順のようなものでしょうか。
明日までなので勝手ですが詳しくお願いします。すみません。
PADは、フローチャートみたいなものですよね。
ソースを、細かく日本語に置き換えてから、PADの記述子に置き換えるとやりやすいですよ。
NQueen関数部分さえ置き換えられれば完成のはず。
PADだと、反復が簡単にかけますから、そう難しくはないはず。
簡単に説明すると、
引数 i 列目
・0行目からN-1行目までの繰り返し(j)
・(i, j)に置ける？
YES: ・置く。
・まだ置き終わっていない？
YES: ・現在の位置のフラグを立てる
・NQueen(i+1)を呼び出す。
・現在の位置のフラグをクリアする
NO : ・置き終わったので表示。
ということです。言葉に抜けがあるかも。自身で確認を。
# フラグとは、行、斜め方向(２種類)のフラグです
あとは自力でがんばってください。
自力で・・・・(((´д｀)))
上のでわからないのは・・・・あほですかもしや。
でもPADもアルゴリズムも初見状態でいきなり書けるんでしょうか・・・。
お願いします・・・。
お答えをお教えください。
最悪の教えて君ここに極めりですがもう本気で意味不明です。
最悪上のだけで提出しようかと。
お願いします。
PADやフローチャート程度であれば、上の記述を、PADなどの記述子に直してやればOKかと。
基本仕様書にもなりませんけどね^^;
詳細設計書ともなると、変数の意味や、条件の意味も明記せねばなりません。
プログラム設計書だとほぼソースを日本語に訳したような状態。
# 会社の方針にもよるかと思いますが。
アルゴリズムは、数学で言えば公式、化学で言えば化学式です。
ほとんどは暗記ですよ。
数学の問題で公式を複数使うことがあるように、ある問題を解くときには、アルゴリズムを複数組み合わせることになります。
上の文章・ソースを、友達同士で相談して考えてみてはどうでしょう。
先生と仲が良ければ、これを元に教わるというのも手です。
いや、もう今日だしこの授業では
一緒に行ってるやつがいないんですが・・・・。
まぁ、上の書いて出しときます。ありがとうでした。
| ツイート |  |