Ｎクイーン問題について
Ｎクイーン問題とは、ＮxＮの盤面にチェスのクイーンＮ個を、互いに効きが無い（クイーンは縦・横・斜め45度方向に効きがある）状態で配置する問題。
すべてのクイーンの効きに当たらない配置の１つ
column(列)
_4___3___2___1___0_
|---|---|-Q-|---|---|0
+-------------------+
|---|---|---|---|-Q-|1
+-------------------+
|---|-Q-|---|---|---|2 row(行)
+-------------------+
|---|---|---|-Q-|---|3
+-------------------+
|-Q-|---|---|---|---|4
+-------------------+
一般的には８×８のチェス盤を用いる８クイーン問題が有名。
多くのエイトクイーン研究者は盤面の縦横幅を８に固定せず、 ＮxＮの盤面とし、現実的な処理時間で、どのサイズ（Ｎ）までの解を求めることができるかを競っています。
現在、Ｎ２８の解を求めたドレスデン大学が世界一を記録している。詳しくは（１）を参照してください。
N-Queens問題：Ｎクイーン問題（１）第一章 エイトクイーンについて
https://suzukiiichiro.github.io/posts/2023-02-14-01-n-queens-suzuki/
ブルートフォースについて
力まかせ探索は、全ての可能性のある解の候補を体系的に数えあげます。
解の候補が一つ生成される都度、その解の候補が解となるかをチェックします。
解の候補が生成後に「解であるか」をチェックするので「生成検査法（generate and test）」とも呼ばれます。
ブルートフォースの手数は、各列 row には１個のクイーンしか置けないので、Ｎ５の場合は、５＊５＊５＊５＊５＝３１２５となり、５＾５，またはＮ＾Ｎと表記します。
したがって、アルゴリズム的に言えば、「力まかせ探索による Ｎクイーン問題の処理時間は Ｏ（Ｎ＾Ｎ）」となります。
効き筋のチェック
ここでは具体的な説明を割愛しますが、解の候補が生成される都度、以下の効き筋チェック関数が呼び出され、解となりうるかを判定すします。
いわゆるＮ５の場合は、以下のチェック関数が３１２５回実行されることになります。
: 'ブルートフォース版効き筋をチェック';
function check_bluteForce(){
local -i size="$1";
local -i flag=1;
for ((r=1;r<size;++r)){
for ((i=0;i<r;++i)){
#echo `$(($1-$2)) | sed -e "s/^-//g"`;
if (( board[i]>=board[r] ));then
val=$(( board[i]-board[r] ));
else
val=$(( board[r]-board[i] ));
fi
if (( board[i]==board[r] || val==(r-i) ));then
flag=0;
return ;
fi
}
}
flag=1;
[[ $flag -eq 0 ]]
return $?;
}
各列col、行rowと比べて、横、斜め左右４５度方向に置かれていないかをチェックし、効きがあればその時点で 「０」（false)を返します。（縦は最初から一つしか置けない仕組みになっているのでチェックはしません）
効きがまったく無い場合は 「１」（true） を返します。つまり解を発見したということになります。
再帰と非再帰について
これまでは再帰という手法でＮクイーンを解決してきました。
再帰を用いたプログラムソースは比較的シンプルに書くことができるのですが、「自分で自分を呼び出す」というロジックが馴染めない人も多いのではないかと思います。
さらに、再帰は「何が行われているのか」がわかりにくく、「ここは再帰」ということで「ここまでなんとか理解をしてきた」ことも否めません。
では、再帰で書くしかないのでしょうか。
いえ、実は再帰ではなく、非再帰で書くこともできます。
非再帰で書くと、多少プログラムソースは長くはなりますが、メリットとして「再帰よりも速い」「関数呼び出しという負荷がなくなる」「変数の値を保持しておく物理メモリの使用率を最小限に抑えることができる」、といったメリットがあります。
なにより、ＣＰＵでの計算と比べて、およそ１００倍以上高速なＧＰＵでの計算ができます。
ＧＰＵで処理するためにはＧＰＵ−ＣＵＤＡというミドルウェアを使う必要があります。
なんとこのＧＰＵ−ＣＵＤＡは「再帰」に未対応なのです（昔は対応していました）。
ということで、第二章からは「再帰」と「非再帰」を両面で理解しつつ、ＧＰＵでのエイトクイーン実装に向けて頑張って進めていきたいと思います。
ブルートフォース再帰版
ブルートフォース再帰版のプログラムソースは以下のとおりです。
第一章のブルートフォース再帰版をより最適化したものですが、ロジックに大きな変化はありません。
: '再帰版ブルートフォース';
function bluteForce_R(){
local -i row="$1";
local -i size="$2";
local -i col=;
if ((row==size));then
check_bluteForce "$size";
if (( $?==1 ));then
((TOTAL++));
printRecord "$size"; # 出力しないならコメント
fi
else
for(( col=0;col<size;col++ )){
board["$row"]="$col";
bluteForce_R $((row+1)) $size ;
}
fi
}
for文で各行の何row目にクイーンを配置するかを決め、最後まで配置した場合は、check_bluteForce() を呼んで、クイーンの配置が「効き」であるかどうかを判定します。
効きでなければ「解を発見した」として ((TOTAL++))で、解個数をインクリメントします。
ですので、check_bluteForce() 関数は、クイーンの効きを判定する関数となります。
重要なことは、クイーンの配置が終わったら
if ((row==size));then
の条件式に入り、その直後で
check_bluteForce "$size";
を呼び出して、クイーンの配置に問題がないかをチェックします。
check_bluteForce()関数の末尾では以下のようになっています。
[[ $flag -eq 0 ]]
return $?;
これは、$flag が 0 だったら、直前の $flag の値を return するという記述です。
また、受け取り側の function bluteForce_R() の以下の部分ですが、
check_bluteForce "$size";
if (( $?==1 ));then
((TOTAL++));
printRecord "$size"; # 出力しないならコメント
fi
check_bluteForce()関数で、効きの判定を行い、「戻り値が $?==1 」で、効きではないのと判定されたので、解を発見したことになり、((TOTAL++))で合計をインクリメントして、printRecord()のボードレイアウト表示関数によって、クイーンの位置を表示する、というロジックとなります。
ここで bashの豆知識ですが、
if (( $?==1 ));then
となっているのは、check_bluteForce "$size"; で実行した return の変数の値を $? で参照し、「１」であれば、
((TOTAL++));
printRecord "$size"; # 出力しないならコメント
を実行するという処理となっています。
bash では、return よって値を「戻り値」として扱うことができない、と多くの書籍やＷｅｂページで言われていますが、こうした使い方によって、「関数の戻り値を利用することができる」ということを覚えておくと良いでしょう。
printRecord "$size"; # 出力しないならコメント
は、ボードレイアウトのクイーンの位置を配置する出力関数です。
ボードレイアウトの出力
ボードレイアウトの出力関数は以下のとおりです。
: 'ボードレイアウトを出力';
function printRecord(){
size="$1";
echo "$TOTAL";
sEcho=" ";
for((i=0;i<size;i++)){
sEcho="${sEcho}${board[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((i==board[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 "";
}
ブルートフォース非再帰版
ブルートフォース非再帰版のプログラムソースは以下のとおりです。
: '非再帰版ブルートフォース';
function bluteForce_NR(){
local -i row="$1";
local -i size="$2";
for ((i=0;i<size;i++)){ board[$i]=-1; }
while ((row>-1));do
local -i matched=0;
local -i col=0;
for((col=board[row]+1;col<size;col++)){
board[$row]=$col;
matched=1;
break;
}
if ((matched));then
((row++));
if ((row==size));then # 最下部まで到達
((row--));
check_bluteForce "$size"; # 効きをチェック
if (($?==1));then # 直前のreturnを利用
((TOTAL++));
printRecord "$size"; # 出力
fi
fi
else
if ((board[row]!=-1));then
board[$row]=-1;
fi
((row--));
fi
done
}
ブルートフォースのポイント
ブルートフォースのポイントは、
クイーンの配置が終わったら
if ((row==size));then
check_bluteForce "$size";
if (( $?==1 ));then
((TOTAL++));
printRecord "$size"; # 出力しないならコメント
fi
else
その直後でクイーンの効きを判定する check_bluteForce() 関数が呼び出されることです。
check_bluteForce "$size";
３１２５回、クイーンの配置が完了する都度、check_bluteForce()が３１２５回呼び出されるわけです。
プログラムソース
再帰版・非再帰版を含むすべてのプログラムソースは以下のとおりです。
プログラムソース最下部で、再帰と非再帰の実行をコメントアウトで切り替えて実行してください。
#!/usr/bin/bash
declare -i TOTAL=0; # カウンター
#
: 'ボードレイアウトを出力';
function printRecord(){
size="$1";
echo "$TOTAL";
sEcho=" ";
for((i=0;i<size;i++)){
sEcho="${sEcho}${board[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((i==board[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 "";
}
#
: 'ブルートフォース版効き筋をチェック';
function check_bluteForce(){
local -i size="$1";
local -i flag=1;
for ((r=1;r<size;++r)){
for ((i=0;i<r;++i)){
#echo `$(($1-$2)) | sed -e "s/^-//g"`;
if (( board[i]>=board[r] ));then
val=$(( board[i]-board[r] ));
else
val=$(( board[r]-board[i] ));
fi
if (( board[i]==board[r] || val==(r-i) ));then
flag=0;
return ;
fi
}
}
flag=1;
[[ $flag -eq 0 ]]
return $?;
}
#
: '非再帰版ブルートフォース';
function bluteForce_NR(){
local -i row="$1";
local -i size="$2";
for ((i=0;i<size;i++)){ board[$i]=-1; }
while ((row>-1));do
local -i matched=0;
local -i col=0;
for((col=board[row]+1;col<size;col++)){
board[$row]=$col;
matched=1;
break;
}
if ((matched));then
((row++));
if ((row==size));then # 最下部まで到達
((row--));
check_bluteForce "$size"; # 効きをチェック
if (($?==1));then # 直前のreturnを利用
((TOTAL++));
printRecord "$size"; # 出力
fi
fi
else
if ((board[row]!=-1));then
board[$row]=-1;
fi
((row--));
fi
done
}
: '再帰版ブルートフォース';
function bluteForce_R(){
local -i row="$1";
local -i size="$2";
local -i col=;
if ((row==size));then
check_bluteForce "$size";
if (( $?==1 ));then
((TOTAL++));
printRecord "$size"; # 出力しないならコメント
fi
else
for(( col=0;col<size;col++ )){
board["$row"]="$col";
bluteForce_R $((row+1)) $size ;
}
fi
}
# 非再帰版ブルートフォース
# time bluteForce_NR 0 5;
#
# 再帰版ブルートフォース
time bluteForce_R 0 5;
#
exit;
実行結果
実行結果は以下の通りです。
bash-3.2$ bash bluteForce.sh
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/
