前提
該当のソースコードに記載した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の盤のどの列にクイーンが配置されているかの結果が出力されていることは理解できています。
例えば1行目は、0列目の0番目の位置、1列目の5番目の位置、2列目7番目の位置....に5クイーンが置かれている。
該当のソースコード
C言語
#include <unistd.h> void outputchar(char c){ write(1, &c, 1);} int abs(int n){ if (n > 0) return (n); else return (n * -1);} void alg(char *tab, int queen, int *t_out){ int i; int j; if (queen == 10) { queen = 0; while (queen < 10) outputchar(tab[queen++] + 48); outputchar('\n'); (*t_out)++; return ; } i = -1; while (++i < 10) { j = 0; while (j < queen && i != tab[j] && abs(tab[j] - i) != queen - j) j++; if (j >= queen) { tab[queen] = i; alg(tab, queen + 1, t_out); } }} int ten_queens_puzzle(void){ char arr[10]; int que; int total_out; que = 0; total_out = 0; alg(arr, que, &total_out); return (total_out);} int main(void){ ten_queens_puzzle(); return (0);}
0 コメント