バックトラック
バックトラック
• DFSであるパスをそれ以上深く辿れない時，一つ前
の状態に戻って別のパスを辿る
→この操作をバックトラック（後戻り）と呼ぶ
• ８クィーン問題
チェス盤面で，お互いの利き筋（縦，横，斜め）にの
らないように8個のクィーンを配置する問題．92通り
の解がある．バックトラックの代表的適用問題．
http://web.hc.keio.ac.jp/~fujimura/index.html
Q
http://www.kawa.net/works/js/8queens/nqueens.html
Q
Q
Q
Q
Q
８クイーンの出力例
Q
・
・
・
・
・
・
・
・
・
Q
・
・
・
・
・
・
・
・
・
・
・
Q
・
・
・
・
・
・
Q
・
・
・
・
・
・
Q
・
・
・
・
・
・
Q
・
・
・
・
・
・
・
・
・
・
・
Q
・
Q
・
・
・
・
・
・
・
Q
・
・
・
・
・
・
・
・
・
・
・
・
・
Q
・
・
・
Q
・
・
・
・
・
・
・
・
Q
・
・
・
・
・
・
・
・
Q
・
・
・
・
・
・
・
・
Q
・
・
・
Q
・
・
・
・
・
Q
・
・
・
・
・
・
・
(a)
(b)
一次元配列 q[0]-q[7]でクィーンの配置を記述する．添え字を列に対応させる．
左図は[0,4,7,5,2,6,1,3]．右図は？
q[0]-q[7]までDFSでサーチする
Put-Q(x):クィーンの置ける位置=ｑ［ｘ]の値を決める．
初期値 q[x]=0
増分 1 (q[x]=q[x]+1)
終了条件q[x]<=8
バックトラッキングの様子
深さ優先探索 jpgファイル参照
PUT-Q(0)
q［x］= 0
PUT-Q(1)
PUT-Q(2)
PUT-Q(5)
○
○
○
3
4
PUT-Q(4)
○
1
2
PUT-Q(3)
○
5
6
7
○
×
× ×
0
0
Q
1
2
1
2
3
Qx
Q
3
4
4
Qx
Q
7
6
7
Q ・・
・・
・
・
・・
・・
・
・
・
・
・
・・・ Q ・
・ Q ・・・
・・・・ Q
・・
Q ・・
・・ Q
・・・
・ Q ・
・
・
・
・
・・
・・
・・
Q・
・・
(a)
１番目の解
5
6
5
Q
Qx
q[0]-q[7]までDFSでサーチする
Put-Q(x):クィーンの置ける位置=ｑ［ｘ]の値を決める．
初期値 q[x]=0
増分 1 (q[x]=q[x]+1)
終了条件q[x]<=8
・
・
・
・
・
アルゴリズム概要
• 左から右へ、上から下へ、置ける場所を探す
• ある行に置けたら、その右の列の上から置ける場所を探す
• ある列のどこにも置けないと判ったら、ひとつ左の列の置
ける場所を探す作業を継続する
• 一番右の列で置ける場所が見つかったら、一丁あがり
• さらに他の解も探すのであれば、ひとつ下の行の続きを探
す。一番左の列の置ける位置を全部調べ終わるまで続け
る
解が見つかったあとの
バックトラッキングの様子
強制バックトラックによる全解探査
PUT-Q(6)
PUT-Q(7)
q［x］= 0
1
○
クイーンの
配置を表示
2
3
4
5
6
7
●
８クィーンメインルーチン
開始
PUT-Q(0)
終了
PUT-Q(x)
q［x］←0
クィーンの置ける位置
=ｑ［ｘ]の値を決める．
c ← CHK-Q(x,q［x］)
false
true
＝
≠
PUT-Q(x＋1)
PRT-Q
q［x］←q［x］＋1
＜
≧
戻る
(b)
PUT-Q(x)
q［x］←0
クィーンの置ける位置
=ｑ［ｘ]の値を決める．
c←CHK-Q(x,q［x］)
false
c
true
X:7
＝
≠
PUT-Q(x＋1)
PRT-Q
q［x］←q［x］＋1
＜
q[x]:8
≧
戻る
(b)
CHK-Q(x，y)
利き筋のチェック
i←0
＝
≠
＝
≠
＝
≠
i←i＋1
＜
≧
ret←true
retを返す
(a)
ret←false
CHK-Q(x，y)
利き筋のチェック
i←0
＝
q[i]:y
≠
＝
≠
＝
≠
i←i＋1
＜
i:x
≧
ret←true
retを返す
(a)
ret←false
CHK-Q(x，y)
利き筋のチェック
i←0
＝
q[i]:y
≠
q[i]:y-x+i
＝
行－列が同じ
→右下がりチェック
＝
行＋列が同じ
→右上がりチェック
≠
q[i]:y+x-i
≠
i←i＋1
＜
i:x
≧
ret←true
retを返す
(a)
行が同じ
→横チェック
ret←false
PRT-Q
ループA
iの初期値0
増分1
i ≧8
結果表示の
サブルーチン
ループB
jの初期値0
増分1
j ≧8
q［j］：i
＝
Qを出力
ループB
改行を出力
ループA
戻る
(b)
≠
．を出力