配置フラグ
各列、対角線上にクイーンがあるかどうかのフラグを用意して高速化を図ります。
これまでもやっていたわけですが、そこの部分を「配置フラグ」と呼ぶことを覚えておいてください。
前回までは以下のように表記していました。
for(( col=0;col<size;col++ )){
aBoard[$row]="$col";
if (( down[col]==0 && right[row-col+size-1]==0 && left[row+col]==0));then
down[$col]=1;
right[$row-$col+($size-1)]=1;
left[$row+$col]=1;
N-Queens05 "$((row+1))" "$size" ;
down[$col]=0;
right[$row-$col+($size-1)]=0;
left[$row+$col]=0;
fi
}
down[] right[] down[]変数の添字の中で毎回計算をしていますね。
ソースも見にくくなっていました。
今回は、ifの手前で down,right,leftの添字の値をそれぞれ保存しておいて、ifの中では計算せずに計算された値が格納されている変数を参照するだけにます。
これでもわずかばかりですが高速化が見込めます。
なにより、以降で進む「ビットマップ」への足がかりとして必要なステップなのです。
for(( col=0;col<size;col++ )){
aBoard[$row]="$col";
dx=$col;
rx=$((row-col+size-1));
lx=$((row+col));
if (( !down[dx] && !right[rx] && !left[lx]));then
down[$dx]=1; right[$rx]=1; left[$lx]=1;
N-Queens06 "$((row+1))" "$size" "$((dx))" "$((rx))" "$((lx))";
down[$dx]=0; right[$rx]=0; left[$lx]=0;
fi
}
また、
N-Queens06 "$((row+1))" "$size" "$((dx))" "$((rx))" "$((lx))";
ここで、N-Queens06にわたすパラメータが３つ増えていることに気が付きましたか？
まだ、さほど効果は期待できませんが、再帰で今ある値を次の再帰に渡す。というテクニックです。
いずれ、ここらへんもしっかり身につけていきましょう。
今は、深く考える必要はありません。
if (( !down[dx] && !right[rx] && !left[lx]));then
Ｃ言語に慣れ親しんでいる人は数値の「０」はFalse、「１」はTrueという理解だと思います。
NOの０（ゼロ）とおぼえましょう。
で、変数は１がTrueなので、
if (( down ));then
fi
これは、
# (( down )) と同じ
if (( down==1 ));then
fi
と同じことなのです。
ですので、
if (( !down ));then
fi
これは、
# ((!down )) と同じ
if (( down==0 ));then
fi
と同じです。
ですので、以下のif文は丁寧に ==0 としていますが、ソースを簡略して書くことができます。
if (( down[dx]==0 && right[rx]==0 && left[lx]==0));then
は、
if (( !down[dx] && !right[rx] && !left[lx]));then
と、同じなのです、ここまでを以下のソースにまとめました
ソース全体は以下のとおりです。
#!/usr/bin/bash
declare -i TOTAL=0; # カウンター
declare -i UNIQUE=0; # ユニークユーザー
: '
エイトクイーン 配置フラグ
';
function N-Queens06(){
local -i row="$1";
local -i size="$2";
local -i col=0; # 再帰に必要
local -i dx="$3";
local -i rx="$4";
local -i lx="$5";
if (( row==size ));then
((TOTAL++));
# echo -n "$COUNT:"
# for(( i=0;i<size;i++ )){
# echo -n "${aBoard[i]} "
# }
# echo "";
else
for(( col=0;col<size;col++ )){
aBoard[$row]="$col";
dx=$col;
rx=$((row-col+size-1));
lx=$((row+col));
if (( !down[dx] && !right[rx] && !left[lx]));then
down[$dx]=1; right[$rx]=1; left[$lx]=1;
N-Queens06 "$((row+1))" "$size" "$((dx))" "$((rx))" "$((lx))";
down[$dx]=0; right[$rx]=0; left[$lx]=0;
fi
}
fi
}
#
function NQ(){
local -i max=15;
local -i min=4;
local -i N="$min";
local startTime=0;
local endTime=0;
local hh=mm=ss=0;
echo " N: Total Unique hh:mm:ss" ;
for((N=min;N<=max;N++)){
TOTAL=0;
UNIQUE=0;
startTime=$(date +%s);# 計測開始時間
N-Queens06 0 "$N";
endTime=$(date +%s); # 計測終了時間
ss=$((endTime-startTime));# hh:mm:ss 形式に変換
hh=$((ss/3600));
ss=$((ss%3600));
mm=$((ss/60));
ss=$((ss%60));
printf "%2d:%13d%13d%10d:%.2d:%.2d\n" $N $TOTAL $UNIQUE $hh $mm $ss ;
}
}
#
NQ;
bash-3.2$ bash N-Queens06.sh
N: Total Unique hh:mm:ss
4: 2 0 0:00:00
5: 10 0 0:00:00
6: 4 0 0:00:00
7: 40 0 0:00:00
8: 92 0 0:00:01
9: 352 0 0:00:03
10: 724 0 0:00:16
11: 2680 0 0:01:22
bash-3.2$
だんだん、それっぽくなってきましたね。
次もお楽しみに！
参考リンク
以下の詳細説明を参考にしてください。
【参考リンク】Ｎクイーン問題 過去記事一覧
【Github】エイト・クイーンのソース置き場 BashもJavaもPythonも！
Ｎクイーン問題（５０）第七章 マルチプロセス Python編
https://suzukiiichiro.github.io/posts/2023-06-21-04-n-queens-suzuki/
Ｎクイーン問題（４９）第七章 マルチスレッド Python編
https://suzukiiichiro.github.io/posts/2023-06-21-03-n-queens-suzuki/
Ｎクイーン問題（４８）第七章 シングルスレッド Python編
https://suzukiiichiro.github.io/posts/2023-06-21-02-n-queens-suzuki/
Ｎクイーン問題（４７）第七章 クラス Python編
https://suzukiiichiro.github.io/posts/2023-06-21-01-n-queens-suzuki/
Ｎクイーン問題（４６）第七章 ステップＮの実装 Python編
https://suzukiiichiro.github.io/posts/2023-06-16-02-n-queens-suzuki/
Ｎクイーン問題（４５）第七章 キャリーチェーン Python編
https://suzukiiichiro.github.io/posts/2023-06-16-01-n-queens-suzuki/
Ｎクイーン問題（４４）第七章 対象解除法 Python編
https://suzukiiichiro.github.io/posts/2023-06-14-02-n-queens-suzuki/
Ｎクイーン問題（４３）第七章 ミラー Python編
https://suzukiiichiro.github.io/posts/2023-06-14-01-n-queens-suzuki/
Ｎクイーン問題（４２）第七章 ビットマップ Python編
https://suzukiiichiro.github.io/posts/2023-06-13-05-n-queens-suzuki/
Ｎクイーン問題（４１）第七章 配置フラグ Python編
https://suzukiiichiro.github.io/posts/2023-06-13-04-n-queens-suzuki/
Ｎクイーン問題（４０）第七章 バックトラック Python編
https://suzukiiichiro.github.io/posts/2023-06-13-03-n-queens-suzuki/
Ｎクイーン問題（３９）第七章 バックトラック準備編 Python編
https://suzukiiichiro.github.io/posts/2023-06-13-02-n-queens-suzuki/
Ｎクイーン問題（３８）第七章 ブルートフォース Python編
https://suzukiiichiro.github.io/posts/2023-06-13-01-n-queens-suzuki/
Ｎクイーン問題（３７）第六章 C言語移植 その１７ pthread並列処理完成
https://suzukiiichiro.github.io/posts/2023-05-30-17-n-queens-suzuki/
Ｎクイーン問題（３６）第六章 C言語移植 その１６ pthreadの実装
https://suzukiiichiro.github.io/posts/2023-05-30-16-n-queens-suzuki/
Ｎクイーン問題（３５）第六章 C言語移植 その１５ pthread実装直前版完成
https://suzukiiichiro.github.io/posts/2023-05-30-15-n-queens-suzuki/
Ｎクイーン問題（３４）第六章 C言語移植 その１４
https://suzukiiichiro.github.io/posts/2023-05-30-14-n-queens-suzuki/
Ｎクイーン問題（３３）第六章 C言語移植 その１３
https://suzukiiichiro.github.io/posts/2023-05-30-13-n-queens-suzuki/
Ｎクイーン問題（３２）第六章 C言語移植 その１２
https://suzukiiichiro.github.io/posts/2023-05-30-12-n-queens-suzuki/
Ｎクイーン問題（３１）第六章 C言語移植 その１１
https://suzukiiichiro.github.io/posts/2023-05-30-11-n-queens-suzuki/
Ｎクイーン問題（３０）第六章 C言語移植 その１０
https://suzukiiichiro.github.io/posts/2023-05-30-10-n-queens-suzuki/
Ｎクイーン問題（２９）第六章 C言語移植 その９
https://suzukiiichiro.github.io/posts/2023-05-30-09-n-queens-suzuki/
Ｎクイーン問題（２８）第六章 C言語移植 その８
https://suzukiiichiro.github.io/posts/2023-05-30-08-n-queens-suzuki/
Ｎクイーン問題（２７）第六章 C言語移植 その７
https://suzukiiichiro.github.io/posts/2023-05-30-07-n-queens-suzuki/
Ｎクイーン問題（２６）第六章 C言語移植 その６
https://suzukiiichiro.github.io/posts/2023-05-30-06-n-queens-suzuki/
Ｎクイーン問題（２５）第六章 C言語移植 その５
https://suzukiiichiro.github.io/posts/2023-05-30-05-n-queens-suzuki/
Ｎクイーン問題（２４）第六章 C言語移植 その４
https://suzukiiichiro.github.io/posts/2023-05-30-04-n-queens-suzuki/
Ｎクイーン問題（２３）第六章 C言語移植 その３
https://suzukiiichiro.github.io/posts/2023-05-30-03-n-queens-suzuki/
Ｎクイーン問題（２２）第六章 C言語移植 その２
https://suzukiiichiro.github.io/posts/2023-05-30-02-n-queens-suzuki/
Ｎクイーン問題（２１）第六章 C言語移植 その１
N-Queens問://suzukiiichiro.github.io/posts/2023-05-30-01-n-queens-suzuki/
Ｎクイーン問題（２０）第五章 並列処理
https://suzukiiichiro.github.io/posts/2023-05-23-02-n-queens-suzuki/
Ｎクイーン問題（１９）第五章 キャリーチェーン
https://suzukiiichiro.github.io/posts/2023-05-23-01-n-queens-suzuki/
Ｎクイーン問題（１８）第四章 エイト・クイーンノスタルジー
https://suzukiiichiro.github.io/posts/2023-04-25-01-n-queens-suzuki/
Ｎクイーン問題（１７）第四章 偉人のソースを読む「Ｎ２４を発見 Ｊｅｆｆ Ｓｏｍｅｒｓ」
https://suzukiiichiro.github.io/posts/2023-04-21-01-n-queens-suzuki/
Ｎクイーン問題（１６）第三章 対象解除法 ソース解説
https://suzukiiichiro.github.io/posts/2023-04-18-01-n-queens-suzuki/
Ｎクイーン問題（１５）第三章 対象解除法 ロジック解説
https://suzukiiichiro.github.io/posts/2023-04-13-02-nqueens-suzuki/
Ｎクイーン問題（１４）第三章 ミラー
https://suzukiiichiro.github.io/posts/2023-04-13-01-nqueens-suzuki/
Ｎクイーン問題（１３）第三章 ビットマップ
https://suzukiiichiro.github.io/posts/2023-04-05-01-nqueens-suzuki/
Ｎクイーン問題（１２）第二章 まとめ
https://suzukiiichiro.github.io/posts/2023-03-17-02-n-queens-suzuki/
Ｎクイーン問題（１１）第二章 配置フラグの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-17-01-n-queens-suzuki/
Ｎクイーン問題（１０）第二章 バックトラックの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-16-01-n-queens-suzuki/
Ｎクイーン問題（９）第二章 ブルートフォースの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-14-01-n-queens-suzuki/
Ｎクイーン問題（８）第一章 まとめ
https://suzukiiichiro.github.io/posts/2023-03-09-01-n-queens-suzuki/
Ｎクイーン問題（７）第一章 ブルートフォース再び
https://suzukiiichiro.github.io/posts/2023-03-08-01-n-queens-suzuki/
Ｎクイーン問題（６）第一章 配置フラグ
https://suzukiiichiro.github.io/posts/2023-03-07-01-n-queens-suzuki/
Ｎクイーン問題（５）第一章 進捗表示テーブルの作成
https://suzukiiichiro.github.io/posts/2023-03-06-01-n-queens-suzuki/
Ｎクイーン問題（４）第一章 バックトラック
https://suzukiiichiro.github.io/posts/2023-02-21-01-n-queens-suzuki/
Ｎクイーン問題（３）第一章 バックトラック準備編
https://suzukiiichiro.github.io/posts/2023-02-14-03-n-queens-suzuki/
Ｎクイーン問題（２）第一章 ブルートフォース
https://suzukiiichiro.github.io/posts/2023-02-14-02-n-queens-suzuki/
Ｎクイーン問題（１）第一章 エイトクイーンについて
https://suzukiiichiro.github.io/posts/2023-02-14-01-n-queens-suzuki/
