前回までのあらすじ
前回の記事では、エイトクイーンの３つのルール
１．縦に一つだけのクイーン
２．横に一つだけのクイーン
３．斜めに一つだけのクイーン
の「１．縦に一つだけのクイーン」を実現する方法を紹介しました。
Ｎ５の時の実行結果ですが、
:
:
:
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
Ｎ５の場合、３１２５ステップかかりました。
このステップは計算で算出することが可能です。
５＊５＊５＊５＊５＝３１２５
Ｎ^Ｎ＝３１２５
ということになります。
こうした、可能性のあるすべての解を体系的に「ちからまかせ」に数え上げる方法を、ブルートフォースといいます。
今回は、抑制ルールを１つ加えます。
今回は、前回のルールに加え、「２．横に一つだけのクイーン」を追加します。
要するに、縦にも横にもクイーンの効きが当たらないように配置するということになります。
そういう意味で、前回は「ブルートフォース」、今回は少し手を入れている分、「バックトラック準備編」という位置づけでご説明します。
次回は、エイトクイーンの解決方法の金字塔「バックトラック」の完成です。
考え方
これまでのクイーンの並びは、以下のような並びであってもカウントしていました。
（できたということにしていました）
column(列)
_4___3___2___1___0_
|-Q-|-Q-|-Q-|-Q-|-Q-|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
今回からは、縦列に一つのクイーンというルールに加えてさらに、「横行にも一つのクイーンしかおけないからね」というルールが追加されるわけです。
まず、スタート段階はクイーンは0列目に一つ(0,0)クイーンを配置します。
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|---|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
次に１列目にクイーンを配置します。
(1,0)は(0,0)のクイーンの効きとなります。
よって１列目のクイーンは(1,1)に配置されます。
以下のようになります。
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|---|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
次は2列目ですが、(2,0)も置けません。
同様に(2,1)も置けません。
結果、(2,2)に配置することになります。
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|-Q-|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
こうして続けていくと、以下のような形で５列全てにクイーンが配置されることになります。
4,3,2,1,0
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|-Q-|---|---|2 row(行)
+-------------------+
|---|-Q-|---|---|---|3
+-------------------+
|-Q-|---|---|---|---|4
+-------------------+
縦（各列）に一つだけのクイーン、というルールに加えて、横（各行）に一つだけのクイーン、というルールが加わり、今回の配置によって「一つの解を見つけた」ということになりました。
列と行に一つだけのクイーンという縛りについての検討は、この画面から考えてみるのが良いのです。
問題は、ここからなのです。
そのまえにソースを以下に示します。
ソース
#!/usr/bin/bash
declare -i COUNT=0; # カウンター
: '
縦と横に１つだけのクイーン
';
function N-Queens03(){
local -i min="$1";
local -i size="$2";
local -i col=0; # 再帰に必要
local -i row=0; # 再帰に必要
local sEcho=""; # 出力用変数
for(( col=0;col<size;col++ )){
if (( down[col] == 0 ));then
pos[$min]="$col";
if (( min==(size-1) ));then
# echo -n "$((COUNT++)): ";
# 画面出力はせず変数に格納
((COUNT++));
for(( row=0;row<size;row++ )){
#echo -n " ${pos[row]} "
# 画面出力はせず変数に格納
#sEcho="${sEcho}${pos[row]} ";
sEcho="${pos[row]} ${sEcho}";
}
# echo ""; # 改行
# ここでまとめて画面に出力
# -n オプションは付けずに改行付きで出力します。
echo "$COUNT: $sEcho" # flush出力
else
down[$col]=1; # trueを代入
N-Queens03 "$((min+1))" "$size" ;
down[$col]=0; # falseを代入
fi
fi
}
}
#
echo "<>３．バックトラック準備編 N-Queens03()";
N-Queens03 0 5;
実行結果
実行結果は以下のとおりです。
$ bash N-Queens03.sh
<>３．バックトラック準備編 N-Queens03()
1: 4 3 2 1 0
2: 3 4 2 1 0
3: 4 2 3 1 0
4: 2 4 3 1 0
5: 3 2 4 1 0
6: 2 3 4 1 0
7: 4 3 1 2 0
8: 3 4 1 2 0
9: 4 1 3 2 0
10: 1 4 3 2 0
11: 3 1 4 2 0
12: 1 3 4 2 0
13: 4 2 1 3 0
14: 2 4 1 3 0
15: 4 1 2 3 0
16: 1 4 2 3 0
17: 2 1 4 3 0
18: 1 2 4 3 0
19: 3 2 1 4 0
20: 2 3 1 4 0
21: 3 1 2 4 0
22: 1 3 2 4 0
23: 2 1 3 4 0
24: 1 2 3 4 0
25: 4 3 2 0 1
26: 3 4 2 0 1
27: 4 2 3 0 1
28: 2 4 3 0 1
29: 3 2 4 0 1
30: 2 3 4 0 1
31: 4 3 0 2 1
32: 3 4 0 2 1
33: 4 0 3 2 1
34: 0 4 3 2 1
35: 3 0 4 2 1
36: 0 3 4 2 1
37: 4 2 0 3 1
38: 2 4 0 3 1
39: 4 0 2 3 1
40: 0 4 2 3 1
41: 2 0 4 3 1
42: 0 2 4 3 1
43: 3 2 0 4 1
44: 2 3 0 4 1
45: 3 0 2 4 1
46: 0 3 2 4 1
47: 2 0 3 4 1
48: 0 2 3 4 1
49: 4 3 1 0 2
50: 3 4 1 0 2
51: 4 1 3 0 2
52: 1 4 3 0 2
53: 3 1 4 0 2
54: 1 3 4 0 2
55: 4 3 0 1 2
56: 3 4 0 1 2
57: 4 0 3 1 2
58: 0 4 3 1 2
59: 3 0 4 1 2
60: 0 3 4 1 2
61: 4 1 0 3 2
62: 1 4 0 3 2
63: 4 0 1 3 2
64: 0 4 1 3 2
65: 1 0 4 3 2
66: 0 1 4 3 2
67: 3 1 0 4 2
68: 1 3 0 4 2
69: 3 0 1 4 2
70: 0 3 1 4 2
71: 1 0 3 4 2
72: 0 1 3 4 2
73: 4 2 1 0 3
74: 2 4 1 0 3
75: 4 1 2 0 3
76: 1 4 2 0 3
77: 2 1 4 0 3
78: 1 2 4 0 3
79: 4 2 0 1 3
80: 2 4 0 1 3
81: 4 0 2 1 3
82: 0 4 2 1 3
83: 2 0 4 1 3
84: 0 2 4 1 3
85: 4 1 0 2 3
86: 1 4 0 2 3
87: 4 0 1 2 3
88: 0 4 1 2 3
89: 1 0 4 2 3
90: 0 1 4 2 3
91: 2 1 0 4 3
92: 1 2 0 4 3
93: 2 0 1 4 3
94: 0 2 1 4 3
95: 1 0 2 4 3
96: 0 1 2 4 3
97: 3 2 1 0 4
98: 2 3 1 0 4
99: 3 1 2 0 4
100: 1 3 2 0 4
101: 2 1 3 0 4
102: 1 2 3 0 4
103: 3 2 0 1 4
104: 2 3 0 1 4
105: 3 0 2 1 4
106: 0 3 2 1 4
107: 2 0 3 1 4
108: 0 2 3 1 4
109: 3 1 0 2 4
110: 1 3 0 2 4
111: 3 0 1 2 4
112: 0 3 1 2 4
113: 1 0 3 2 4
114: 0 1 3 2 4
115: 2 1 0 3 4
116: 1 2 0 3 4
117: 2 0 1 3 4
118: 0 2 1 3 4
119: 1 0 2 3 4
120: 0 1 2 3 4
順を追って見ていきます。
実行結果を順を追ってみていきましょう。
この作業はとても重要です。
この作業をやることなく次に進んでもまったくといってよいほど意味がありません。
理解していなくてもステップを進むことはできますが、理解していないから身につかないのです。
バカバカしいと思わずに、実行結果を順番にボード上のクイーンを配置しつつ、動きを確認してください。
では、実行結果の解を上から順を追ってみていきます。
１つ目の実行結果は
1: 4 3 2 1 0
でした。
この盤面情報を図に置き換えるとどうなりますか？
1: 4 3 2 1 0
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|-Q-|---|---|2 row(行)
+-------------------+
|---|-Q-|---|---|---|3
+-------------------+
|-Q-|---|---|---|---|4
+-------------------+
さてここで、どのクイーンが動くのかというところが重要です。
動くのは盤面の左側である「先っぽ」となります。
とはいえ、(4,4)のクイーンはもう最下部まで到達しています。
再帰では最下部へ到達しているその条件を「基底条件」というのでしたね。
「４列のクイーンはこれ以上手がない状態」といえます。
ここで操作している４列に「↓」マークを付けておきます。
いずれこの矢印が役に立ちます。
↓
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|-Q-|---|---|2 row(行)
+-------------------+
|---|-Q-|---|---|---|3
+-------------------+
|-Q-|---|---|---|---|4
+-------------------+
さて４列にこれ以上「手がない」ということになり初めて、一つ手前３列のクイーンに軸が移動します。
ここでは「↓」が右に一つずれます。
↓
column(列)
_4___3___2___1___0_
|---|-x-|---|---|-Q-|0
+-------------------+
|---|-x-|---|-Q-|---|1
+-------------------+
|---|-x-|-Q-|---|---|2 row(行)
+-------------------+
|---|-Q-|---|---|---|3
+-------------------+
|-Q-|---|---|---|---|4
+-------------------+
軸（↓）にある(3,3)のクイーン可能性のある移動箇所を探します。
(3,0),(3,1),(3,2)はアタリでおけません。
(3,3)は現在の場所となりますし、
(3,4)に移動できそうですね。
盤面は以下のとおりです。
↓
column(列)
_4___3___2___1___0_
|---|-x-|---|---|-Q-|0
+-------------------+
|---|-x-|---|-Q-|---|1
+-------------------+
|---|-x-|-Q-|---|---|2 row(行)
+-------------------+
|---|-x-|---|---|---|3
+-------------------+
|-Q-|-Q-|---|---|---|4
+-------------------+
col3列のクイーンは(3,4)へ移動しました。
となると、ここからcol4列のクイーンの移動が始まります。
(4,0),(4,1),(4,2)まではアタリですね。(4,3)….
(4.3)におけますね。
これで、２つ目の解ができあがります。
盤面は以下のとおりです。
2: 3 4 2 1 0
↓
column(列)
_4___3___2___1___0_
|-x-|---|---|---|-Q-|0
+-------------------+
|-x-|---|---|-Q-|---|1
+-------------------+
|-x-|---|-Q-|---|---|2 row(行)
+-------------------+
|-Q-|-x-|---|---|---|3
+-------------------+
|---|-Q-|---|---|---|4
+-------------------+
(4,4)は(3,4)のクイーンのアタリなので移動できません。
これで「col4列のクイーンはすべての可能性を探し終わった」といえます。
ですので３列のクイーンを桁上りしたいところなのですが、残念ながらcol3のクイーンはすでに最下部へ到達しており、
「３列のクイーンはこれ以上手がない状態」と、なりました。
ここで軸「↓」を col3からcol2へずらします。
↓
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|-Q-|---|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
先程と同様、手がない状態となると「一つ手前の」列である２列のクイーンが「ひとつずれてみようか」と下(2,3)に移動し桁上りします。
元の場所にはわかりやすく「x」マークを付けておきました。
盤面は以下のようになります。
↓
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|-x-|---|---|2 row(行)
+-------------------+
|---|---|-Q-|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
ここからいつもの処理が始まります。
col3 列のクイーンは移動できる可能性を最上部から順にたどります。
(3,0),(3,1)はアタリとなり置けません、(3,2)に置けそうですね。
↓
column(列)
_4___3___2___1___0_
|---|-x-|---|---|-Q-|0
+-------------------+
|---|-x-|---|-Q-|---|1
+-------------------+
|---|-Q-|-x-|---|---|2 row(行)
+-------------------+
|---|---|-Q-|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
ここで４列目の移動候補を最上部から順番にたどります。
(4,0),(4,1),(4,2),(4,3),(4,4)
(4,4)におけますね！
これで３つ目の解が見つかったことになります。
盤面は以下の通りとなります。
3: 4 2 3 1 0
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|---|---|-Q-|0
+-------------------+
|-x-|-x-|---|-Q-|---|1
+-------------------+
|-x-|-Q-|-x-|---|---|2 row(行)
+-------------------+
|-x-|---|-Q-|---|---|3
+-------------------+
|-Q-|---|---|---|---|4
+-------------------+
さて、現在の矢印↓の場所は col2 です。
また、(3,2)のクイーンの位置で展開した col4列で移動できる可能性は上から順にすべて潰しました。
そこで、３列はひとつ下(3,3)にずれます。
アタリですね。
さらにひとつ下の(3,4)にずれます。
↓
column(列)
_4___3___2___1___0_
|---|-x-|---|---|-Q-|0
+-------------------+
|---|-x-|---|-Q-|---|1
+-------------------+
|---|-x-|-x-|---|---|2 row(行)
+-------------------+
|---|-x-|-Q-|---|---|3
+-------------------+
|---|-Q-|---|---|---|4
+-------------------+
さて col4列目の移動候補を気を取り直して上から順番にたどりましょう。
(4,0),(4,1),(4,2)
まず(4,2)へ移動できそうですね。
盤面は以下のとおりです。
ここで４つ目の解ができました。
盤面は以下のとおりです。
4: 2 4 3 1 0
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|---|---|-Q-|0
+-------------------+
|-x-|-x-|---|-Q-|---|1
+-------------------+
|-Q-|-x-|-x-|---|---|2 row(行)
+-------------------+
|---|-x-|-Q-|---|---|3
+-------------------+
|---|-Q-|---|---|---|4
+-------------------+
４列目の続きも見てみましょう。
(4,3),(4,4)はアタリですので置けませんね。
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|---|---|-Q-|0
+-------------------+
|-x-|-x-|---|-Q-|---|1
+-------------------+
|-Q-|-x-|-x-|---|---|2 row(行)
+-------------------+
|-x-|-x-|-Q-|---|---|3
+-------------------+
|-x-|-Q-|---|---|---|4
+-------------------+
col4列目の可能性はすべて潰しました。
さらに３列目(3,4)のクイーンは最下部となりました。
col4 col3 でもう動かせる可能性はありません。
「col2列(2,3)のクイーンはこれ以上手がない」状態なので、
col2列(2,3)のクイーンは(2,4)へ移動します。
盤面は以下のとおりです。
↓
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|-Q-|---|1
+-------------------+
|---|---|-x-|---|---|2 row(行)
+-------------------+
|---|---|-x-|---|---|3
+-------------------+
|---|---|-Q-|---|---|4
+-------------------+
ではいつものとおり col3列目の一番上から可能性をたどっていきます。
(3,0),(3,1),(3,2)
(3,2)に置けそうです。
↓
column(列)
_4___3___2___1___0_
|---|-x-|---|---|-Q-|0
+-------------------+
|---|-x-|---|-Q-|---|1
+-------------------+
|---|-Q-|-x-|---|---|2 row(行)
+-------------------+
|---|---|-x-|---|---|3
+-------------------+
|---|---|-Q-|---|---|4
+-------------------+
では４列目の移動できる可能性を上から順番にたどっていきます。
(4,0),(4,1),(4,2),(4,3)
(4,3)が置けそうです。
解が一つ見つかりました。
5: 3 2 4 1 0
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|---|---|-Q-|0
+-------------------+
|-x-|-x-|---|-Q-|---|1
+-------------------+
|-x-|-Q-|-x-|---|---|2 row(行)
+-------------------+
|-Q-|---|-x-|---|---|3
+-------------------+
|---|---|-Q-|---|---|4
+-------------------+
さらに(4,4)への可能性も探索しますが、あたりなので移動できません。
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|---|---|-Q-|0
+-------------------+
|-x-|-x-|---|-Q-|---|1
+-------------------+
|-x-|-Q-|-x-|---|---|2 row(行)
+-------------------+
|-x-|---|-x-|---|---|3
+-------------------+
|-x-|---|-Q-|---|---|4
+-------------------+
４列のクイーンは一番下まで到達しましたので、(3,2)のクイーンは(3,3)へ移動します。
↓
column(列)
_4___3___2___1___0_
|---|-x-|---|---|-Q-|0
+-------------------+
|---|-x-|---|-Q-|---|1
+-------------------+
|---|-x-|-x-|---|---|2 row(行)
+-------------------+
|---|-Q-|-x-|---|---|3
+-------------------+
|---|---|-Q-|---|---|4
+-------------------+
ではあらためて col4列目のクイーンの移動の可能性を上から順番にたどります。
(4,0),(4,1),(4,2)
(4,2)が置けそうです。
これで一つ解が発見できました。
6: 2 3 4 1 0
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|---|---|-Q-|0
+-------------------+
|-x-|-x-|---|-Q-|---|1
+-------------------+
|-Q-|-x-|-x-|---|---|2 row(行)
+-------------------+
|---|-Q-|-x-|---|---|3
+-------------------+
|---|---|-Q-|---|---|4
+-------------------+
続けて４列目のクイーンを下に移動してたどってみます。
(4,3),(4,4)もあたり
４列の移動候補はすべて潰しました。
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|---|---|-Q-|0
+-------------------+
|-x-|-x-|---|-Q-|---|1
+-------------------+
|-x-|-x-|-x-|---|---|2 row(行)
+-------------------+
|-x-|-Q-|-x-|---|---|3
+-------------------+
|-x-|---|-Q-|---|---|4
+-------------------+
ここで３列目(3,3)のクイーンをひとつ下にずらします。
(3,4)はあたりで移動できませんね。
↓
column(列)
_4___3___2___1___0_
|---|-x-|---|---|-Q-|0
+-------------------+
|---|-x-|---|-Q-|---|1
+-------------------+
|---|-x-|-x-|---|---|2 row(行)
+-------------------+
|---|-x-|-x-|---|---|3
+-------------------+
|---|-x-|-Q-|---|---|4
+-------------------+
３列目のクイーンの移動できる可能性はすべて潰しました。
さらに、矢印↓である col2 列目のクイーンの移動できる可能性はすべて潰しました。
ここで軸「↓」が一つ左にずれて col1 列が軸となり、(1,1)のクイーンをひとつ下に移動させます。
こうした動きが「バックトラック」と言われる理由です。
盤面は以下のとおりです。
↓
column(列)
_4___3___2___1___0_
|---|---|---|---|-Q-|0
+-------------------+
|---|---|---|-x-|---|1
+-------------------+
|---|---|---|-Q-|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
そこで、２列(2,4)のクイーンが移動できる可能性をしらみつぶしに（ブルートフォース）たどっていきます。
(2,1)におけますね。
↓
column(列)
_4___3___2___1___0_
|---|---|-x-|---|-Q-|0
+-------------------+
|---|---|-Q-|-x-|---|1
+-------------------+
|---|---|---|-Q-|---|2 row(行)
+-------------------+
|---|---|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
では、３列目の可能性をたどります。
(3,3)に置けそうです。
↓
column(列)
_4___3___2___1___0_
|---|-x-|-x-|---|-Q-|0
+-------------------+
|---|-x-|-Q-|-x-|---|1
+-------------------+
|---|-x-|---|-Q-|---|2 row(行)
+-------------------+
|---|-Q-|---|---|---|3
+-------------------+
|---|---|---|---|---|4
+-------------------+
では４列目の可能性をたどります。
(4,4)に置けました。
７つ目の解が発見できました。
7: 4 3 1 2 0
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|-x-|---|-Q-|0
+-------------------+
|-x-|-x-|-Q-|-x-|---|1
+-------------------+
|-x-|-x-|---|-Q-|---|2 row(行)
+-------------------+
|-x-|-Q-|---|---|---|3
+-------------------+
|-Q-|---|---|---|---|4
+-------------------+
では３列目の(3,3)を下に一つずらします。
↓
column(列)
_4___3___2___1___0_
|---|-x-|-x-|---|-Q-|0
+-------------------+
|---|-x-|-Q-|-x-|---|1
+-------------------+
|---|-x-|---|-Q-|---|2 row(行)
+-------------------+
|---|-x-|---|---|---|3
+-------------------+
|---|-Q-|---|---|---|4
+-------------------+
４列目の移動候補を上から順番にたどります。
(4,0),(4,1),(4,2),(4,3),
(4,3)に置けそうです。
ここで新たな解が発見できました。
8: 3 4 1 2 0
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|-x-|---|-Q-|0
+-------------------+
|-x-|-x-|-Q-|-x-|---|1
+-------------------+
|-x-|-x-|---|-Q-|---|2 row(行)
+-------------------+
|-Q-|-x-|---|---|---|3
+-------------------+
|-x-|-Q-|---|---|---|4
+-------------------+
ここからは解となる盤面情報表示しておきます。
9: 4 1 3 2 0
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|-x-|---|-Q-|0
+-------------------+
|-x-|-Q-|-x-|-x-|---|1
+-------------------+
|-x-|---|-x-|-Q-|---|2 row(行)
+-------------------+
|-x-|---|-Q-|---|---|3
+-------------------+
|-Q-|---|---|---|---|4
+-------------------+
10: 1 4 3 2 0
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|-x-|---|-Q-|0
+-------------------+
|-Q-|-x-|-x-|-x-|---|1
+-------------------+
|---|-x-|-x-|-Q-|---|2 row(行)
+-------------------+
|---|-x-|-Q-|---|---|3
+-------------------+
|---|-Q-|---|---|---|4
+-------------------+
11: 3 1 4 2 0
↓
column(列)
_4___3___2___1___0_
|-x-|-x-|-x-|---|-Q-|0
+-------------------+
|-x-|-Q-|-x-|-x-|---|1
+-------------------+
|-x-|---|-x-|-Q-|---|2 row(行)
+-------------------+
|-Q-|---|-x-|---|---|3
+-------------------+
|---|---|-Q-|---|---|4
+-------------------+
どうでしょうか？
ボード右側のクイーンよりも左側のクイーンが一生懸命に動いていることが判ります。
軸「↓」は右へ右へとずれていきますね。
この動きが「バックトラック」です。
次の章で本格的なバックトラックの完成となります。
左側のクイーンの移動候補がなくなったら右側のクイーンを一つおろして、左側のクイーンを候補の一番最初に戻し、可能性のある移動を探していましたね。
この処理は以下の部分が大きく影響しています。
down[$col]=1; # trueを代入
N-Queens03 "$((min+1))" "$size" ;
down[$col]=0; # falseを代入
さらに言えば、クイーンの横列の当たり判定部分は以下のとおりです。
if (( down[col] == 0 ));then
ソースの内容を深く理解する必要はありません。
どういう動きになるのかを知ることが重要です。
盤面の移動を何度も確認しておくのが良いです。
これからさらにどんどん複雑な動きとなります。
しっかりとクイーンの動きを理解してください。
Ｎが５のときの計算方法
前回は、縦に一つのクイーン、いわゆる縦の効きだけを考慮しました。
そのＮ５の計算方法は
５＊５＊５＊５＊５＝３１２５
Ｎ＾５＝３１２５ となります。
一般的にこうしたブルートフォースの動きは
Ｎ＾Ｎ
と書きます。
今回は、横の効きも取り入れたことでステップ数は１２０となりました。
計算で出すと以下の通りとなります。
５＊４＊３＊２＊１＝１２０
５！＝１２０
一般的にこうしたバックトラックの動きは
Ｎ！
と書きます。
実行結果
ちなみに、８ｘ８の実行結果は以下の通りです。
<>３．バックトラック準備編 N-Queens03()
1: 7 6 5 4 3 2 1 0
2: 6 7 5 4 3 2 1 0
3: 7 5 6 4 3 2 1 0
4: 5 7 6 4 3 2 1 0
5: 6 5 7 4 3 2 1 0
6: 5 6 7 4 3 2 1 0
7: 7 6 4 5 3 2 1 0
8: 6 7 4 5 3 2 1 0
9: 7 4 6 5 3 2 1 0
10: 4 7 6 5 3 2 1 0
11: 6 4 7 5 3 2 1 0
12: 4 6 7 5 3 2 1 0
13: 7 5 4 6 3 2 1 0
14: 5 7 4 6 3 2 1 0
15: 7 4 5 6 3 2 1 0
16: 4 7 5 6 3 2 1 0
17: 5 4 7 6 3 2 1 0
18: 4 5 7 6 3 2 1 0
19: 6 5 4 7 3 2 1 0
20: 5 6 4 7 3 2 1 0
21: 6 4 5 7 3 2 1 0
22: 4 6 5 7 3 2 1 0
23: 5 4 6 7 3 2 1 0
24: 4 5 6 7 3 2 1 0
25: 7 6 5 3 4 2 1 0
26: 6 7 5 3 4 2 1 0
27: 7 5 6 3 4 2 1 0
28: 5 7 6 3 4 2 1 0
29: 6 5 7 3 4 2 1 0
30: 5 6 7 3 4 2 1 0
:
:
40306: 7 6 5 4 1 2 3 0
40307: 7 6 5 4 1 3 0 2
40308: 7 6 5 4 1 3 2 0
40309: 7 6 5 4 2 0 1 3
40310: 7 6 5 4 2 0 3 1
40311: 7 6 5 4 2 1 0 3
40312: 7 6 5 4 2 1 3 0
40313: 7 6 5 4 2 3 0 1
40314: 7 6 5 4 2 3 1 0
40315: 7 6 5 4 3 0 1 2
40316: 7 6 5 4 3 0 2 1
40317: 7 6 5 4 3 1 0 2
40318: 7 6 5 4 3 1 2 0
40319: 7 6 5 4 3 2 0 1
40320: 7 6 5 4 3 2 1 0
real 0m18.519s
user 0m18.304s
sys 0m0.154s
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/
