ここまでのあらすじ
ここまでのおさらいと整理・まとめをしておきたいと思います。
（１）ではエイトクイーンについてを説明しました。先人の方々の努力や現在までの経緯などをリンクも交えて紹介しました。
N-Queens問題：Ｎクイーン問題（１）について
https://suzukiiichiro.github.io/posts/2023-02-14-01-n-queens-suzuki/
（２）では解は出しはしませんでしたが「ブルートフォース」について説明しました。
ブルートフォースは、すべてのステップを出しつつ、解を求める方法で、Ｎ５の場合は５＊５＊５＊５＊５＝３１２５ステップも必要となります。これを ５＾５ または Ｎ＾Ｎと表記することも説明してきました。
N-Queens問題：Ｎクイーン問題（２）ブルートフォース
https://suzukiiichiro.github.io/posts/2023-02-14-02-n-queens-suzuki/
（３）ではバックトラックの前準備として縦だけではなく横の制約もいれて「縦方向と横方向の効き」を活かした方法を紹介しました。
ステップは ５＊４＊３＊２＊１＝１２０ステップですみます。これを ５！ または Ｎ！ と表記することも説明してきました。
こちらの方法はバックトラックと言われる「縦と横と斜め」の効きについての一歩手前の処理と言えます。
（３）の段階では、バックトラックといえども、まだ斜めの効きはまだ考慮されていませんが、ブルートフォースと異なり、処理をする中で、「可能性がなければ前のトラックに戻って処理をすすめる」という効率的なアプローチとなります。
N-Queens問題：Ｎクイーン問題（３）バックトラック準備編
https://suzukiiichiro.github.io/posts/2023-02-14-03-n-queens-suzuki/
（４）では、「縦横斜めの効き」を考慮した「バックトラック」をご紹介しました。Ｎ５の解は１０と出ました。 これまでのアプローチと比べてとても高速でした。
N-Queens問題：Ｎクイーン問題（４）バックトラック
https://suzukiiichiro.github.io/posts/2023-02-21-01-n-queens-suzuki/
実は、この（４）の手法は、（５）の「配置フラグ」を使っています。
第二章で厳格な違いをご説明し、ソースも添付します。
現段階では、曖昧に「バックトラック」と「配置フラグ」が「ある」ということだけ覚えておいてください。
（５）では、今後、処理が複雑なり、同時に処理が高速化するに連れ、Ｎを増やして見たくなることを想定して、進捗表示テーブルを作成しました。
これにより、Ｎは４，５，６，７，８・・・と連続して処理をすることができます。
N-Queens問題：Ｎクイーン問題（６）配置フラグ
https://suzukiiichiro.github.io/posts/2023-03-07-01-n-queens-suzuki/
（６）では、制約テスト「配置フラグ」を導入しました。ソースの可読性が高まるだけではなく、今後ご紹介する「ビットマップ」への橋渡しとして、必要なステップです。こちらは先にご説明したとおり、正しい配置フラグの説明ではありません。
きちんと「バックトラック」と「配置フラグ」の違いを第二章で明確に説明します。
N-Queens問題：Ｎクイーン問題（５）進捗表示テーブルの作成
https://suzukiiichiro.github.io/posts/2023-03-06-01-n-queens-suzuki/
（７）では、一番初めに紹介しておきながら、クイーンの位置を列挙することにとどめて、解を出すことのなかった「ブルートフォース」を改造して解を出しました。
N-Queens問題：Ｎクイーン問題（７）ブルートフォース再び
https://suzukiiichiro.github.io/posts/2023-03-07-01-n-queens-suzuki/
なぜ、「ブルートフォース」の完成形の紹介がこれほどまでに遅くなったのか？
それは、ブルートフォースですべての可能性を列挙することは（２）で紹介したとおりですが、そこから解を導き出すための処理は（６）までのスキルが必要だからです。という説明をしました。
今回の（８）では、これまでやってきた処理を整理して一枚のソースのまとめ、シェルスクリプトでメニュー画面を作り、これまでやってきた各ステップの実行を簡単に切り替えて比較したりして動作させることができるようになります。
メニュー画面
メニュー画面は以下のイメージで作ります。
実行するとメインメニューが表示され、行頭の番号を入力すると項目が実行されます。
bash-3.2$ bash N-Queens08.sh
エイト・クイーン メニュー
実行したい番号を選択
7) ブルートフォース （７）
6) 配置フラグ （６）
4) バックトラック （４）
3) 縦と横の制約 （３）
2) 縦のみの制約 （２）
echo 行頭の番号を入力してください;
行末の全角数字は、エイトクイーンのシリーズ番号です。
プログラムは、多少手を入れましたが、これまで紹介したソースの構造をおおよそ踏襲しています。
一枚のソースで動きます。
以下のソースをファイルに保存して実行してください。
ファイル名はシリーズ番号に揃えて N-Queens08.shとしました。
ソース
ソースは以下のとおりです。
#!/usr/bin/bash
declare -i COUNT=0;
declare -i TOTAL=0; # カウンター
declare -i UNIQUE=0; # ユニークユーザー
#
: 'ブルートフォース用レコードを出力';
function printRecordBF(){
echo "$TOTAL:";
sEcho=" ";
for((i=0;i<size;i++)){
sEcho="${sEcho}${col[i]} ";
}
echo "$sEcho";
echo -n "+";
for((i=0;i<size;i++)){
echo -n "-";
if((i<(size-1)));then
echo -n "+";
fi
}
echo "+";
for((i=0;i<size;i++)){
echo -n "|";
for((j=0;j<size;j++)){
#if((j==col[i]));then
if((i==col[j]));then
echo -n "O";
else
echo -n " ";
fi
if((j<(size-1)));then
echo -n "|";
fi
}
echo "|";
if((i<(size-1)));then
echo -n "+";
for((j=0;j<size;j++)){
echo -n "-";
if((j<(size-1)));then
echo -n "+";
fi
}
echo "+";
fi
}
echo -n "+";
for((i=0;i<size;i++)){
echo -n "-";
if((i<(size-1)));then
echo -n "+";
fi
}
echo "+";
echo "";
}
#
: 'abs関数をbashで実装';
function abs_diff {
echo $(($1 >= $2 ? $1 - $2 : $2 - $1))
}
#
: 'ブルートフォースで解を出す';
function check(){
local -i size="$1";
for(( i=(size-1);i>=0;i-- )){
col[$i]=${board[i]};
for(( j=i+1;j<size;j++ )){
if(( col[i]<=col[j] ));then
(( col[j]++ ));
fi
}
}
for(( i=0;i<size;i++ )){
for(( j=i+1;j<size;j++ )){
tmp=`abs_diff "${col[$i]}" "${col[$j]}"`;
tm2=`abs_diff "$j" "$i"`;
if(( tmp==tm2 ));then
return 0;
fi
}
}
(( TOTAL++ ));
printRecordBF;
}
#
: 'ブルートフォースで解を出す';
function N-Queens06(){
local -i row="$1";
local -i size="$2";
local -i col=;
if(( row==size ));then
check "$size";
else
for(( col=0;col<(size-row);col++ )){
board["$row"]="$col";
N-Queens06 $((row+1)) $size ;
}
fi
}
#
: 'レコードを出力';
printRecord(){
sEcho="$COUNT: ";
for((i=0;i<size;i++)){
sEcho="${sEcho}${aBoard[i]} ";
}
echo "$sEcho";
}
#
: '配置フラグ';
function N-Queens05(){
local -i row="$1";
local -i size="$2";
local -i col=; # 再帰に必要
local sEcho="";
local dx="$3"; # 再帰に必要
local rx="$4"; # 再帰に必要
local lx="$5"; # 再帰に必要
for((col=0;col<size;col++)){
dx=$col;
rx=$((row+col));
lx=$((row-col+(size-1)));
if((!down[dx]
&& !right[rx]
&& !left[lx]));then
aBoard[$row]="$col";
if((row==(size-1)));then
((TOTAL++));
else
down[$dx]=1;
right[$rx]=1;
left[$lx]=1;
N-Queens05 "$((row+1))" "$size";
down[$dx]=0;
right[$rx]=0;
left[$lx]=0;
fi
fi
}
}
#
: 'バックトラック';
function N-Queens04(){
local -i row="$1";
local -i size="$2";
local -i col=; # 再帰に必要
local sEcho="";
for((col=0;col<size;col++)){
if((!down[col]
&& !right[row+col]
&& !left[row-col+(size-1)]));then
aBoard[$row]="$col";
if((row==(size-1)));then
((COUNT++));
printRecord;
else
down[$col]=1;
right[$row+$col]=1;
left[$row-$col+($size-1)]=1;
N-Queens04 "$((row+1))" "$size";
down[$col]=0;
right[$row+$col]=0;
left[$row-$col+($size-1)]=0;
fi
fi
}
}
#
: '横の制約を追加';
function N-Queens03(){
local -i row="$1";
local -i size="$2";
local -i col=; # 再帰に必要
local sEcho="";
for((col=0;col<size;col++)){
if((!down[col]));then
aBoard[$row]="$col";
if((row==(size-1)));then
((COUNT++));
printRecord;
else
down[$col]=1;
N-Queens03 "$((row+1))" "$size";
down[$col]=0;
fi
fi
}
}
#
: '縦のみの制約';
function N-Queens02(){
local -i row="$1";
local -i size="$2";
local -i col=; # 再帰に必要
local sEcho="";
for((col=0;col<size;col++)){
aBoard[$row]="$col";
if((row==(size-1)));then
((COUNT++));
printRecord;
else
N-Queens02 "$((row+1))" "$size";
fi
}
}
#
function NQ(){
local selectName="$1";
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);# 計測開始時間
"$selectName" 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 ;
}
}
while :
do
read -n1 -p "
エイト・クイーン メニュー
実行したい番号を選択
7) ブルートフォース （７）
6) 配置フラグ （６）
4) バックトラック （４）
3) 縦と横の制約 （３）
2) 縦のみの制約 （２）
echo "行頭の番号を入力してください";
" selectNo;
echo
case "$selectNo" in
7)
N-Queens06 0 5; # ブルートフォース
break;
;;
6)
NQ "N-Queens05"; # 配置フラグ
break;
;;
4)
N-Queens04 0 5; # バックトラック
break;
;;
3)
N-Queens03 0 5; # 縦と横の制約
break;
;;
2)
N-Queens02 0 5; # 縦のみの制約
break;
;;
*)
;;
esac
done
exit;
実行結果
実行結果は以下のとおりです。
bash-3.2$ bash N-Queens08.sh
エイト・クイーン メニュー
実行したい番号を選択
7) ブルートフォース （７）
6) 配置フラグ （６）
4) バックトラック （４）
3) 縦と横の制約 （３）
2) 縦のみの制約 （２）
echo 行頭の番号を入力してください;
7
1:
0 2 4 1 3
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
2:
0 3 1 4 2
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
3:
1 3 0 2 4
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
4:
1 4 2 0 3
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
5:
2 0 3 1 4
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
6:
2 4 1 3 0
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
7:
3 0 2 4 1
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
8:
3 1 4 2 0
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
9:
4 1 3 0 2
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
10:
4 2 0 3 1
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
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/
