質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.02%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Q&A

解決済

10クイーン(Nクイーン)問題(C言語)の再帰関数による解法(アルゴリズム)について解説して下さい(コード提出済み)

iq180
usan

総合スコア3

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

2回答

0グッド

0クリップ

410閲覧

投稿2022/10/25 07:33

編集2022/10/25 12:07

前提

該当のソースコードに記載した10クイーン問題の再帰関数による解法(アルゴリズム)をわかりやすく解説して下さい。

実現したいこと

以下のソースコードの「alg関数」がどのようなアルゴリズムとなっているのか、できればわかりやすく説明していただくことはできますか?
特に、alg関数の「while (j < queen && i != tab[j] && abs(tab[j] - i) != queen - j)」以降の部分が何をしているのか理解することができておりません。
何卒宜しくお願い致します。

試したこと

以下のソースコードを実行すると以下の結果が出力されます。

0257948136
0258693147
0258693174
0286931475
0358297146
(中略)
9713068524
9741306825
9741306852
9742051863

10×10の盤のどの行にクイーンが配置されているかの結果が出力されていることは理解できています。
例えば最初の出力の0257948136は、0列目の0行目の位置、1列目の2行目の位置、2列目の5行目の位置、3列目7行目の位置....にクイーンが置かれていることを示している。

該当のソースコード

C言語

1#include <unistd.h> 2 3void outputchar(char c) 4{ 5 write(1, &c, 1); 6} 7 8int abs(int n) 9{ 10 if (n > 0) 11 return (n); 12 else 13 return (n * -1); 14} 15 16void alg(char *tab, int queen, int *t_out) 17{ 18 int i; 19 int j; 20 21 if (queen == 10) 22 { 23 queen = 0; 24 while (queen < 10) 25 outputchar(tab[queen++] + 48); 26 outputchar('\n'); 27 (*t_out)++; 28 return ; 29 } 30 i = -1; 31 while (++i < 10) 32 { 33 j = 0; 34 while (j < queen && i != tab[j] && abs(tab[j] - i) != queen - j) 35 j++; 36 if (j >= queen) 37 { 38 tab[queen] = i; 39 alg(tab, queen + 1, t_out); 40 } 41 } 42} 43 44int ten_queens_puzzle(void) 45{ 46 char arr[10]; 47 int que; 48 int total_out; 49 50 que = 0; 51 total_out = 0; 52 alg(arr, que, &total_out); 53 return (total_out); 54} 55 56int main(void) 57{ 58 ten_queens_puzzle(); 59 return (0); 60} 61

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

2022/10/25 07:37依頼された後にこの質問は修正されています

こちらの質問が他のユーザーから「やってほしいことだけを記載した丸投げの質問」という指摘を受けました。

jimbe

2022/10/25 07:45 編集

ご自身で考えて書いたコードでは無いということでしょうか。 (わざと分かり難く書いているような感じがしますが。)
iq180

2022/10/25 07:48 編集

そうなのです。 確かに理解しにくいです。 しかし、このような質問の仕方はあまりよろしくないということですね。
fana

2022/10/25 07:55

そもそも真っ当なコードなのですか? ぱっと見で,件の関数は int i; の未初期化がヤバそうに見えるのですが…?
iq180

2022/10/25 07:59

出力例を追記しましたが、このコードでは、10クイーン問題の724通りの配置方法を出力することが出来ています。
fana

2022/10/25 08:08 編集

あ,見間違いでした.すみません. i = -1; って普通に書いてありますね.(とてもはずかしい)
jimbe

2022/10/25 08:08

i=-1 がありますけど。 Nクイーンは総当たりやバックトラック(今回はこれでしょうね)の解説記事が多くあると思うのですが、それらは参考にならなかったでしょうか。
iq180

2022/10/25 08:15

ご回答ありがとうございます。バックトラックの記事を参考にさせて頂きます。

回答2

2

弄り過ぎて(見た目)別物になってしまってます・・・。

c

1#include <stdio.h> 2 3#define N 10 4 5//表示 6void print(int *table) { 7 for(int i=0; i<N; i++) putchar(table[i] + '0'); 8 putchar('\n'); 9} 10// i と j が横に衝突していたら !0 11int collisionSideways(int *table, int i, int j) { 12 return table[i] == table[j]; //行が同じ 13} 14// i と j が斜めに衝突していたら !0 15int collisionDiagonally(int *table, int i, int j) { 16 return abs(table[i] - table[j]) == abs(i - j); //行と列のそれぞれの差の絶対値が同じなら衝突 Ex: (1,2)-(3,4), (1,7)-(4,4) 17} 18//クイーン衝突判定(column と 0~column-1 の何れかとが衝突していたら !0) 19int judgment(int *table, int column) { 20 int collision = 0; //衝突無 21 for(int j=0; j<column && !collision; j++) { 22 collision = collisionSideways(table, column, j) || collisionDiagonally(table, column, j); 23 } 24 return collision; 25} 26 27int alg(int *table, int column) { 28 if(column == N) { //全部終わっていたら表示 29 print(table); 30 return 1; 31 } 32 33 int count = 0; 34 for(int row=0; row<N; row++) { 35 table[column] = row; 36 if(!judgment(table, column)) count += alg(table, column+1); //衝突していなければ次の列 37 } 38 return count; 39} 40 41int main(void) { 42 int table[N]; 43 printf("count=%d\n", alg(table, 0)); 44}

実行結果

plain

10257948136 20258693147 30258693174 40286931475 50358297146 6(中略) 79641702853 89713068524 99741306825 109741306852 119742051863 12count=724

投稿2022/10/25 09:43

編集2022/10/25 14:31
jimbe

総合スコア10800

usan, fana😄を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

iq180

2022/10/25 10:00

大変参考になります! こちらの解法も理解できるように努めます!! ご回答いただきありがとうございます!

2

ベストアンサー

読み難いものは,同等の読みやすいものに書き換えていくと把握しやすいのではないでしょうか.
こんな話かと.

t_out は使われていないので取っ払いました)

C

1void alg(char *tab, int queen /*, int *t_out*/) 2{ 3 //結果出力 4 if (queen == 10) 5 { 6 queen = 0; 7 while (queen < 10) 8 putchar(tab[queen++] + 48); 9 putchar('\n'); 10 //(*t_out)++; 11 return ; 12 } 13 14 //この列の全候補(10個のマス)について処理する 15 for( int iPos=0; iPos<10; ++iPos ) 16 { 17 //queen列目のクイーンを 18 //iPos番目のマス(行)に置けるであろうか? 19 //これは直前の列までに配置されたクイーンの場所を見て判断する 20 //(:tab[0] から tab[queen-1] の内容を見てチェック) 21 int itab = 0; 22 for( /*NOP*/; itab<queen; ++itab ) 23 { 24 if( iPos == tab[itab] )break; //既存クイーンと同じ行には並べられない 25 if( abs( tab[itab]-iPos ) == queen - itab )break; //既存クイーンと斜めの位置には並べられない 26 } 27 28 //↑で途中でbreakした場合,itabの値はqueenの値に達していない. 29 //すなわち,ここのifは,「iPos番目にクイーンを置けるなら」という条件. 30 if(itab >= queen) 31 { 32 tab[queen] = iPos; //結果を格納 33 alg(tab, queen + 1 /*, t_out*/); //次の列へ 34 } 35 } 36}

投稿2022/10/25 08:28

fana

総合スコア10670

jimbe, usan😄を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

fana

2022/10/25 08:30

変数 i と j は見間違いやすいのでてきとーに別の名前に変えた.
iq180

2022/10/25 08:32

詳細にご回答いただきありがとうございます!! 参考にさせて頂き、今から理解に努めます!!!
iq180

2022/10/25 14:40

こちらの回答で先に理解するに至りました。 お二方にお答えいただいてどちらの回答にも感謝しております。 ありがとうございました。

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。