Ｎクイーンについて簡単に
ではさっそくＮクイーン問題を考えてみましょう。
この章では、可能性のあるすべての解を体系的に数え上げる方法を考えてみます。
こういった「ちからまかせ」に数え上げる方法を、ブルートフォースといいます。
今回は、Ｎクイーンを「ブルートフォース」で考えてみるということになります。
効き筋について
column(列)
_4___3___2___1___0_
|---|-*-|---|-*-|---|0
+-------------------+
|---|---|-*-|-*-|-*-|1
+-------------------+
|-*-|-*-|-*-|-Q-|-*-|2 row(行)
+-------------------+
|---|---|-*-|-*-|-*-|3
+-------------------+
|---|-*-|---|-*-|---|4
+-------------------+
チェスで言うところのクイーンの動きは、縦、横、斜めに直線の効き筋を持っています。
将棋の飛車と角を足した動きがクイーンです。
チェス盤は縦８ｘ横８のサイズなのですが、この章では少し小さめの５ｘ５で考えてみます。
この場合、Ｎが５ということで「５クイーン」と言われることが多いです。
さて５クイーンのルールは、
１．各縦（列）に一つのクイーンがある。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|-Q-|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
この場合、横の効き筋が効いてしまいますね。
横一列にクイーンが配置されるのは、エイトクイーンのルールではありえませんが、今回はわかりやすくするために「置きます」。
column(列)
_4___3___2___1___0_
|-Q-|-*-|-*-|-*-|-*-|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
ということで、エイト・クイーンは、
１．縦に一つだけのクイーン
２．横に一つだけのクイーン
３．斜めに一つだけのクイーン
の３つを満たしている必要があります。
とはいえ、この章では、「縦の効き筋」のことだけを考えて作っていきます。
ですので「横の効き筋」と「斜めの効き筋」のことは一旦忘れてください。
クイーンの動きを１手ずつ見てみます
では、まずはクイーンを動かしてみましょう。
プログラムの動きに合わせて説明していきたいと思います。
第一手目、0,0のクイーンをひとつ下に移動します。
col0,row0のクイーンはcol0,row1に移動しました。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|---|0
+-------------------+
|---|---|---|---|-Q-|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
さらにクイーンをひとつ下に移動します。
col0,row1からcol0,row2へ移動しました。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|---|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|-Q-|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
さらにひとつ下に移動します。
col0,row3へ移動しました。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|---|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|-Q-|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
さらにひとつ下に移動します。
col0,row4へ移動しました。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|---|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|-Q-|4
+-------------------+
ここでcol0,row4のクイーンは一番下の最下部まで到達し、もうこれ以上下に行けなくなりました。
ここで桁上りの処理で、col0列のクイーンはcol0,row0へ戻り、col1,row0のクイーンがひとつ下に移動します。
図で表すと以下のようになります。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|---|-Q-|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
ここからは先程の動きの繰り返しで、col0列のクイーンは一つずつ下に最下部へ到達するまでおりていきます。
col0,row1へ移動しました。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|---|---|0
+-------------------+
|---|---|---|-Q-|-Q-|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
さらに下に移動します。
col0,row2へ移動しました。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|---|---|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|---|---|-Q-|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
さらに下に移動します。
col0,row3へ移動しました。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|---|---|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|-Q-|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
さらに下に移動します。
col0,row4へ移動しました。
col0列のクイーンは最下部へ到達しました。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|---|---|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|-Q-|4
+-------------------+
ここで先程と同様、col0,row4のクイーンはcol0,row0へ戻り、col1列のクイーンはcol1,row2へ移動します。
図で表すと以下のようになります。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|---|-Q-|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|-Q-|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
クイーンは、最下部へ到達すると、最上部へ戻り、左隣のクイーンがひとつ下に降ります。
さて、以下の場合はどうなりますか？
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|---|---|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|-Q-|-Q-|4
+-------------------+
この場合は、col1,row4のクイーンと、col0,row4のクイーンは最上部にもどります。
同時に、col2列のクイーンがcol2,row1へ移動します。
図で表すと以下のとおりです。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|---|-Q-|-Q-|0
+-------------------+
|---|---|-Q-|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
このことからわかるように、col0列のクイーンは最も反復が多く、次にcol1列目、col2列目、col3列目のクイーンが忙しく動くことがわかります。
最下部に到達したら、最上部へ戻り、左隣のクイーンを一つ下げる。という処理を繰り返し行います。
処理完了直前の状態から
では、処理が終わる直前の状態として以下の場合は考えてみましょう。
col4列目、col3列目、col2列目、col1列目のクイーンが最下部にあるとします。
col0列目のクイーンが順を追って最下部へ向かって移動を繰り返します。
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|-Q-|-Q-|-Q-|-Q-|---|4
+-------------------+
col0列目のクイーンが最下部へ到達すると処理は終了します。
処理が終了したときのボード画面は以下のとおりです。
column(列)
_4___3___2___1___0_
|---|---|---|---|---|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|-Q-|-Q-|-Q-|-Q-|-Q-|4
+-------------------+
ボードの動きを数値で表す
プログラムで処理するので、ボードの盤面を数字で表すことにします。
例えば下のボード画面は、
col4 col3 col2 col1 col0
の row の場所を使って
0,0,0,0,0 とします。
0,0,0,0,0
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|-Q-|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
以下の場合は、0,0,0,0,1となります。
0,0,0,0,1
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|---|0
+-------------------+
|---|---|---|---|-Q-|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
以下は、0,0,0,0,2 となります。
0,0,0,0,2
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|---|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|-Q-|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
以下は、0,0,0,1,0となります。
0,0,0,1,0
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|---|-Q-|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
以下はどうなりますか？
0,0,0,4,4
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|---|---|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|-Q-|-Q-|4
+-------------------+
0,0,0,4,4となります。
また、処理終了直前のボード画面が以下の通りだったとします。
4,4,4,4,0
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|-Q-|-Q-|-Q-|-Q-|---|4
+-------------------+
4,4,4,4,0 ですね。
以下は、処理が終了した状態で4,4,4,4,4 となります。
4,4,4,4,4
column(列)
_4___3___2___1___0_
|---|---|---|---|---|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|-Q-|-Q-|-Q-|-Q-|-Q-|4
+-------------------+
挙動をプログラムに置き換えてみます。
(※)この章の挙動は、各行に１個のクイーンを配置する組み合わせを列挙するだけで、Ｎクイーン問題を解いているわけではありません。
というのも、今回の説明では、
そもそもエイト・クイーンにある３つのルール
１．縦列に一つだけのクイーン
２．横列に一つだけのクイーン
３．斜め列に一つだけのクイーン
の１を満たしているに過ぎません。
ということで、気を取り直して
N-Queens02.sh ファイルを作成してください。
#!/usr/bin/bash
function N-Queens02(){
: # まだなにもない
}
#
function NQ(){
echo "<>１．ブルートフォース（力まかせ探索） N-Queens02()";
N-Queens02 0 5;
}
#
NQ;
ファイルを実行するとファイル最下部の NQが実行され、function NQ()が呼び出されます。
現在のfunction NQ()はechoと N-Queens02()関数の呼び出しがあるだけです。
N-Queens02 0 5;
N-Queens02()関数に、２つのパラメータ 0 と 8 の２つのパラメータ（値）を渡しています。
function N-Queens02()関数を追記します。
さっそく NQ() から N-Queens02() へ渡した２つのパラメータを、N-Queens02()関数の冒頭で明示的に変数へ代入しましょう。
function N-Queens02(){
local -i min="$1";
local -i size="$2";
}
変数前についている local は、この関数でのみ有効な変数であることを示しており、-i は、変数に代入される値が「整数」であることを明示的に指定しています。
関数パラメータの $1 や $2 といった変数は、関数に渡された変数の順番です。
N-Queens02 0 5;
１つ目のパラメータは 0 なので $1に、２つ目のパラメータは 5 なので、$2 として関数に渡されます。
関数内で、$1 $2 としてプログラムを表記しても動作しますが、ソースの可読性（読みやすさ）が落ちてしまいます。
関数の冒頭で、きちんとわかりやすい変数名に代入してあげることが望ましいです。
また、$1 や $2の代入は、必ずダブルクォーテーションで囲みましょう。
function N-Queens02(){
local -i min="$1";
local -i size="$2";
}
ここまでのソースは以下のとおりです。
#!/usr/bin/bash
: '
ブルートフォース 力まかせ探索
';
function N-Queens02(){
local -i min="$1";
local -i size="$2";
}
#
function NQ(){
# ブルートフォース 力まかせ探索
N-Queens02 0 5;
}
#
NQ;
forループ
次は、forループ部分についてです。
最も激しく動いていたクイーンは col0 列のクイーンでした。
逆に、もっとも動きの小さなクイーンは col4 列のクイーンでした。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|---|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|-Q-|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
こうしたクイーンの動きは、
この場合、２つのforループで表現します。
外側のforループはcolを表します。
for(( 外側の col が ０から４へ順番に )){
for(( 内側の row が０から４へ順番に )){
}
}
外側(col)のforループの作成
では、５ｘ５の５クイーンをプログラム化します。
最初に、colの動きを表す外側の for ループを作りましょう。
col0 列目から順を追ってcol1，col2，col3，col4 列目までたどっていきます。
# sizeは `5`
for((col=0;col<size;col++)){
: # まだなにもない
: # `col` は０から４へ順番に
}
さて、デバッグも兼ねて動きをひとつひとつ見ていくことにします。
おすすめの方法は、実行しながら処理のステップを順を追って、目視で確認することです。
以下のコマンドをプログラムに埋め込むことにします。
read -p "なにかキーを入力してください"
さらにコメント部分に、ウォッチしておきたい変数を埋め込みます。
具体的には以下のソースを見てください。
#!/usr/bin/bash
: '
ブルートフォース 力まかせ探索
';
function N-Queens02(){
local -i min="$1";
local -i size="$2";
for((col=0;col<size;col++)){
pos[$min]="$col";
read -p "col: $col size: $size min: $min";
}
}
#
function NQ(){
# ブルートフォース 力まかせ探索
N-Queens02 0 5;
}
#
NQ;
実行結果は以下のとおりです。
bash-3.2$ bash N-Queens02.sh
col: 0 size: 5 min: 0
col: 1 size: 5 min: 0
col: 2 size: 5 min: 0
col: 3 size: 5 min: 0
col: 4 size: 5 min: 0
bash-3.2$
col が ０から４まで移動しているのが判りますね。
外側のループ col は左方向へ順にたどっていきます。
← ← ← ← ←
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|-Q-|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
内側(row)のforループの作成
次は row の縦移動を作ってみます。
この動きは、外側の for ループの内側にもう一つ for ループを作成し、col ごとに row の動きを表現します。
クイーンの row (縦)の動きを表現すると以下の通りになります。
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|-Q-|0 ↓
+-------------------+
|---|---|---|---|---|1 ↓
+-------------------+
|---|---|---|---|---|2 row(行)↓
+-------------------+
|---|---|---|---|---|3 ↓
+-------------------+
|---|---|---|---|---|4 ↓
+-------------------+
では、内側の for ループを追記したソースは以下のとおりです。
read -p で出力を確認することができてとても便利です。
#!/usr/bin/bash
: '
ブルートフォース 力まかせ探索
';
function N-Queens02(){
local -i min="$1";
local -i size="$2";
for((col=0;col<size;col++)){
pos[$min]="$col";
for((row=0;row<size;row++)){
read -p "col: $col row: $row size: $size min: $min";
}
}
}
#
function NQ(){
echo "<>１．ブルートフォース（力まかせ探索） N-Queens02()";
N-Queens02 0 5;
}
#
NQ;
実行結果は以下のとおりです。
bash-3.2$ bash N-Queens02.sh
<>１．ブルートフォース（力まかせ探索） N-Queens02()
col: 0 row: 0 size: 5 min: 0
col: 0 row: 1 size: 5 min: 0
col: 0 row: 2 size: 5 min: 0
col: 0 row: 3 size: 5 min: 0
col: 0 row: 4 size: 5 min: 0
col: 1 row: 0 size: 5 min: 0
col: 1 row: 1 size: 5 min: 0
col: 1 row: 2 size: 5 min: 0
col: 1 row: 3 size: 5 min: 0
col: 1 row: 4 size: 5 min: 0
col: 2 row: 0 size: 5 min: 0
col: 2 row: 1 size: 5 min: 0
col: 2 row: 2 size: 5 min: 0
col: 2 row: 3 size: 5 min: 0
col: 2 row: 4 size: 5 min: 0
col: 3 row: 0 size: 5 min: 0
col: 3 row: 1 size: 5 min: 0
col: 3 row: 2 size: 5 min: 0
col: 3 row: 3 size: 5 min: 0
col: 3 row: 4 size: 5 min: 0
col: 4 row: 0 size: 5 min: 0
col: 4 row: 1 size: 5 min: 0
col: 4 row: 2 size: 5 min: 0
col: 4 row: 3 size: 5 min: 0
col: 4 row: 4 size: 5 min: 0
bash-3.2$
row が ０から４まで順に進み、最下部まで到達したら、０に戻り同時に、左隣の col が一つインクリメントします。
再帰を使って書いてみます
ここまでの処理を再帰を使って書いてみます。
まずは、ソースを見てください。
#!/usr/bin/bash
: '
ブルートフォース 力まかせ探索
';
function N-Queens02(){
local -i min="$1";
local -i size="$2";
for((col=0;col<size;col++)){
pos[$min]="$col";
if((min==size-1));then
for((row=0;row<size;row++)){
echo -n " ${pos[row]} "
}
echo ""; # 改行
else
N-Queens02 "$((min+1))" "$size";
fi
}
}
#
function NQ(){
echo "<>１．ブルートフォース（力まかせ探索） N-Queens02()";
N-Queens02 0 5;
}
#
NQ;
実行結果は以下のとおりです。
bash-3.2$ bash N-Queens.sh
0 0 0 0 1
0 0 0 0 2
0 0 0 0 3
0 0 0 0 4
bash-3.2$
あれ？
col0 の処理で終わってしまっていますね。
colが左に桁上りできずにいるようです。
この理由は、再帰処理に使われる変数の定義が原因なのです。
以下の２行を関数の冒頭に加えるだけで動くようになります。
local -i col=0; # 再帰に必要
local -i row=0; # 再帰に必要
重要なこと
N-Queens02 "$((min+1))" "$size";
$((min+1))
の部分はインクリメントしているわけですが、
$((min++))
では動きません。
明示的に min+1 とする必要があります。
あと、min==size-1 といった基底条件を忘れずに。
上記のことを含めたソースは以下のとおりです。
#!/usr/bin/bash
: '
ブルートフォース 力まかせ探索
';
function N-Queens02(){
local -i min="$1";
local -i size="$2";
local -i col=0; # 再帰に必要
local -i row=0; # 再帰に必要
for((col=0;col<size;col++)){
pos[$min]="$col";
if((min==size-1));then
for((row=0;row<size;row++)){
#read -p "col: $col row: $row size: $size min: $min";
echo -n " ${pos[row]} "
}
echo ""; # 改行
else
N-Queens02 "$((min+1))" "$size";
fi
}
}
#
function NQ(){
echo "<>１．ブルートフォース（力まかせ探索） N-Queens02()";
N-Queens02 0 5;
}
#
NQ;
実行結果
<>１．ブルートフォース（力まかせ探索） N-Queens02()
0 0 0 0 0
0 0 0 0 1
0 0 0 0 2
0 0 0 0 3
0 0 0 0 4
0 0 0 1 0
0 0 0 1 1
0 0 0 1 2
0 0 0 1 3
:
:
:
4 4 4 1 2
4 4 4 1 3
4 4 4 1 4
4 4 4 2 0
4 4 4 2 1
4 4 4 2 2
4 4 4 2 3
4 4 4 2 4
4 4 4 3 0
4 4 4 3 1
4 4 4 3 2
4 4 4 3 3
4 4 4 3 4
4 4 4 4 0
4 4 4 4 1
4 4 4 4 2
4 4 4 4 3
4 4 4 4 4
なんか動くようになりました!
すべてのコマが４となっていることから分かる通り、５つのクイーンは最下部へ到達して処理が終了していることが判ります。
echo コマンドで２つの便利
echo -n は、出力する際に改行を行わないオプションです。
連続して出力されますので、空白を含めています。
else の直前で echo "" を使って改行を行っています。
カウンターの設置
さて、どのくらいのステップが必要となるのかも知りたいところです。
カウンター COUNT 変数をソースの冒頭で宣言してみます。
宣言するために declareを、-i は変数は整数を扱うことを明示的にしてしています。
カウンターは０で初期化しています。
declare -i COUNT=0;
インクリメントの仕方
if 文の直後で COUNT をインクリメントしています。
インクリメントの方法は、letコマンドやbcコマンドなど色々ありますが、最も完結でわかりやすい ((COUNT++)) で実行できます。
改行無しで出力する理由ですが、次に続く、クイーンの位置情報を右に連結したいからです。
((COUNT++)); # インクリメント
echo -n "$COUNT: "; # 改行無しで出力
ここまでのソースは以下のとおりです。
#!/usr/bin/bash
declare -i COUNT=0;
: '
ブルートフォース 力まかせ探索
';
function N-Queens02(){
local -i min="$1";
local -i size="$2";
local -i col=0; # 再帰に必要
local -i row=0; # 再帰に必要
for((col=0;col<size;col++)){
pos[$min]="$col";
if((min==size-1));then
((COUNT++));
echo -n "$COUNT:"
for((row=0;row<size;row++)){
echo -n "${pos[row]} "
}
echo ""; # 改行
else
N-Queens02 "$((min+1))" "$size";
fi
}
}
#
function NQ(){
echo "<>１．ブルートフォース（力まかせ探索） N-Queens02()";
N-Queens02 0 5;
}
#
NQ;
実行結果は以下のとおりです。
<>１．ブルートフォース（力まかせ探索） N-Queens02()
1:0 0 0 0 0
2:0 0 0 0 1
3:0 0 0 0 2
4:0 0 0 0 3
5:0 0 0 0 4
6:0 0 0 1 0
7:0 0 0 1 1
8:0 0 0 1 2
9:0 0 0 1 3
10:0 0 0 1 4
11:0 0 0 2 0
12:0 0 0 2 1
13:0 0 0 2 2
14:0 0 0 2 3
15:0 0 0 2 4
16:0 0 0 3 0
:
:
:
3092:4 4 3 3 1
3093:4 4 3 3 2
3094:4 4 3 3 3
3095:4 4 3 3 4
3096:4 4 3 4 0
3097:4 4 3 4 1
3098:4 4 3 4 2
3099:4 4 3 4 3
3100:4 4 3 4 4
3101:4 4 4 0 0
3102:4 4 4 0 1
3103:4 4 4 0 2
3104:4 4 4 0 3
3105:4 4 4 0 4
3106:4 4 4 1 0
3107:4 4 4 1 1
3108:4 4 4 1 2
3109:4 4 4 1 3
3110:4 4 4 1 4
3111:4 4 4 2 0
3112:4 4 4 2 1
3113:4 4 4 2 2
3114:4 4 4 2 3
3115:4 4 4 2 4
3116:4 4 4 3 0
3117:4 4 4 3 1
3118:4 4 4 3 2
3119:4 4 4 3 3
3120:4 4 4 3 4
3121:4 4 4 4 0
3122:4 4 4 4 1
3123:4 4 4 4 2
3124:4 4 4 4 3
3125:4 4 4 4 4
速度の最適化
処理時間は速いに越したことありません。
プログラムの処理速度のボトルネックの多くは、ファイルの入出力処理部分、もしくは画面への出力です。
echo を抑制する
echo -n は 外側の for でも出力していますが、もっとも回転回数の多い内側の for は外側の回数とは比較にならないほど多くの「出力」がされています。
この２箇所の出力は画面に出力することなく、変数に入れるだけにして、内側の for を抜けたときにまとめて画面出力することが速度改善に繋がります。
ソースは以下のとおりです。
#!/usr/bin/bash
declare -i COUNT=0; # カウンター
: '
ブルートフォース 力まかせ探索
';
function N-Queens02(){
local -i min="$1";
local -i size="$2";
local -i col=0; # 再帰に必要
local -i row=0; # 再帰に必要
local sEcho=""; # 出力用変数
for((col=0;col<size;col++)){
pos[$min]="$col";
if((min==size-1));then
((COUNT++));
# echo -n "$COUNT:"
# 画面出力はせず変数に格納
sEcho="$COUNT: ";
for((row=0;row<size;row++)){
#echo -n " ${pos[row]} "
# 画面出力はせず変数に格納
sEcho="${sEcho}${pos[row]} ";
}
# echo ""; # 改行
# ここでまとめて画面に出力
# -n オプションは付けずに改行付きで出力します。
echo "$sEcho" # flush出力
else
N-Queens02 "$((min+1))" "$size"; # 再帰
fi
}
}
#
function NQ(){
echo "<>２．ブルートフォース（力まかせ探索） N-Queens02()";
N-Queens02 0 5;
}
#
NQ;
今は、Ｎが５ですからそんなに変化はないかもしれません。
いずれ、Ｎが７，８、、、１５，１６・・・。
爆発的に処理が膨らまないうちに、色々工夫をしておいたほうが良さそうです。
Ｎ５の計算方法
Ｎが５の時の実行結果終了部分をみてみると・・・
:
:
:
3117:4 4 4 3 1
3118:4 4 4 3 2
3119:4 4 4 3 3
3120:4 4 4 3 4
3121:4 4 4 4 0
3122:4 4 4 4 1
3123:4 4 4 4 2
3124:4 4 4 4 3
3125:4 4 4 4 4
Ｎ５の場合、３１２５ステップかかりました。
このステップは計算で算出することが可能です。
５＊５＊５＊５＊５＝３１２５
Ｎ^Ｎ＝３１２５
ということになります。
８ｘ８の出力結果
参考までに８ｘ８の実行結果は以下のとおりです。
以下の部分を８とすればよいですね。
# N-Queens02 0 5;
N-Queens02 0 8;
実行方法
$ bash N-Queens02.sh
<>１．ブルートフォース（力まかせ探索） N-Queens02()
1: 0 0 0 0 0 0 0 0
2: 0 0 0 0 0 0 0 1
3: 0 0 0 0 0 0 0 2
4: 0 0 0 0 0 0 0 3
5: 0 0 0 0 0 0 0 4
6: 0 0 0 0 0 0 0 5
7: 0 0 0 0 0 0 0 6
8: 0 0 0 0 0 0 0 7
9: 0 0 0 0 0 0 1 0
10: 0 0 0 0 0 0 1 1
11: 0 0 0 0 0 0 1 2
12: 0 0 0 0 0 0 1 3
13: 0 0 0 0 0 0 1 4
14: 0 0 0 0 0 0 1 5
15: 0 0 0 0 0 0 1 6
16: 0 0 0 0 0 0 1 7
17: 0 0 0 0 0 0 2 0
18: 0 0 0 0 0 0 2 1
19: 0 0 0 0 0 0 2 2
20: 0 0 0 0 0 0 2 3
21: 0 0 0 0 0 0 2 4
22: 0 0 0 0 0 0 2 5
23: 0 0 0 0 0 0 2 6
24: 0 0 0 0 0 0 2 7
25: 0 0 0 0 0 0 3 0
26: 0 0 0 0 0 0 3 1
27: 0 0 0 0 0 0 3 2
28: 0 0 0 0 0 0 3 3
29: 0 0 0 0 0 0 3 4
30: 0 0 0 0 0 0 3 5
31: 0 0 0 0 0 0 3 6
32: 0 0 0 0 0 0 3 7
33: 0 0 0 0 0 0 4 0
34: 0 0 0 0 0 0 4 1
35: 0 0 0 0 0 0 4 2
36: 0 0 0 0 0 0 4 3
37: 0 0 0 0 0 0 4 4
38: 0 0 0 0 0 0 4 5
39: 0 0 0 0 0 0 4 6
40: 0 0 0 0 0 0 4 7
41: 0 0 0 0 0 0 5 0
42: 0 0 0 0 0 0 5 1
43: 0 0 0 0 0 0 5 2
44: 0 0 0 0 0 0 5 3
45: 0 0 0 0 0 0 5 4
46: 0 0 0 0 0 0 5 5
47: 0 0 0 0 0 0 5 6
48: 0 0 0 0 0 0 5 7
49: 0 0 0 0 0 0 6 0
50: 0 0 0 0 0 0 6 1
51: 0 0 0 0 0 0 6 2
52: 0 0 0 0 0 0 6 3
53: 0 0 0 0 0 0 6 4
54: 0 0 0 0 0 0 6 5
55: 0 0 0 0 0 0 6 6
56: 0 0 0 0 0 0 6 7
57: 0 0 0 0 0 0 7 0
58: 0 0 0 0 0 0 7 1
59: 0 0 0 0 0 0 7 2
60: 0 0 0 0 0 0 7 3
61: 0 0 0 0 0 0 7 4
62: 0 0 0 0 0 0 7 5
63: 0 0 0 0 0 0 7 6
64: 0 0 0 0 0 0 7 7
65: 0 0 0 0 0 1 0 0
66: 0 0 0 0 0 1 0 1
67: 0 0 0 0 0 1 0 2
68: 0 0 0 0 0 1 0 3
69: 0 0 0 0 0 1 0 4
70: 0 0 0 0 0 1 0 5
71: 0 0 0 0 0 1 0 6
72: 0 0 0 0 0 1 0 7
73: 0 0 0 0 0 1 1 0
:
:
:
:
16777193: 7 7 7 7 7 7 5 0
16777194: 7 7 7 7 7 7 5 1
16777195: 7 7 7 7 7 7 5 2
16777196: 7 7 7 7 7 7 5 3
16777197: 7 7 7 7 7 7 5 4
16777198: 7 7 7 7 7 7 5 5
16777199: 7 7 7 7 7 7 5 6
16777200: 7 7 7 7 7 7 5 7
16777201: 7 7 7 7 7 7 6 0
16777202: 7 7 7 7 7 7 6 1
16777203: 7 7 7 7 7 7 6 2
16777204: 7 7 7 7 7 7 6 3
16777205: 7 7 7 7 7 7 6 4
16777206: 7 7 7 7 7 7 6 5
16777207: 7 7 7 7 7 7 6 6
16777208: 7 7 7 7 7 7 6 7
16777209: 7 7 7 7 7 7 7 0
16777210: 7 7 7 7 7 7 7 1
16777211: 7 7 7 7 7 7 7 2
16777212: 7 7 7 7 7 7 7 3
16777213: 7 7 7 7 7 7 7 4
16777214: 7 7 7 7 7 7 7 5
16777215: 7 7 7 7 7 7 7 6
16777216: 7 7 7 7 7 7 7 7
real 43m42.887s
user 42m39.067s
sys 0m41.138s
bash-3.2$
４３分かかりました。^^;
16777216: 77777777
16,777,216 １千６百７７万ステップもかかりましたね。
Ｎ８の計算方法
Ｎ８の場合は、１６，７７７，２１６ステップかかりました
このステップも計算で算出することが可能です。
８＊８＊８＊８＊８＊８＊８＊８＝１６，７７７，２１６
Ｎ^８＝１６，７７７，２１６
ということになります。
ひとこと
今回は、縦列に一つだけのクイーンを配置するという一つのルールで処理しました。
次回は、横行に一つだけのクイーンを配置するというルールを追加して処理してみます。
次回からは以下の配置はだめなのです。
縦にも横にも１つのクイーンしか置けません。
column(列)
row(行)_0___1___2___3___4_
0|-Q-|-Q-|---|---|---|
+-------------------+
1|---|---|---|---|---|
+-------------------+
2|---|---|---|---|---|
+-------------------+
3|---|---|---|---|---|
+-------------------+
4|---|---|---|---|---|
+-------------------+
以下なら「よし」という感じです。
では次回をお楽しみに。
column(列)
row(行)_0___1___2___3___4_
0|-Q-|---|---|---|---|
+-------------------+
1|---|-Q-|---|---|---|
+-------------------+
2|---|---|---|---|---|
+-------------------+
3|---|---|---|---|---|
+-------------------+
4|---|---|---|---|---|
+-------------------+
参考リンク
以下の詳細説明を参考にしてください。
【参考リンク】Ｎクイーン問題 過去記事一覧
【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/
