バックトラックアルゴリズム

アルゴリズムとデータ構造
補足資料10-2
「nクイーン」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
バックトラックアルゴリズム
• とりあえずやってみる
• ダメなら戻って別の道を探る
– あのとき別の道を選んでいたら、、、
• 試行錯誤(trial and error)
– 結局全部のケースをやってみる(完全解)
nクイーン(n-queens)
• チェスの「クイーン」
nクイーン(n-queens)
• チェスの「クイーン」、n x nの盤面上で、
n個のクイーンが
お互いに取らない
(効き筋にならない)
ように配置
nクイーン(n-queens)
• この問題を解くためのデータ構造
nクイーン(n-queens)
• この問題を解くためのデータ構造
column 列
row 行
row = 0
row = 1
row = 2
row = 3
row = 4
col = 0
col = 1
col = 2
col = 3
col = 4
nクイーン(n-queens)
• この問題を解くためのデータ構造
column 列
row 行
• すでに効き筋 row = 0
→FALSE
row = 1
• queenを置ける
row = 2
→TRUE
col = 0
col = 1
col = 2
col = 3
col = 4
TRUE
FALSE
TRUE
FALSE
TRUE
FALSE
FALSE
FALSE
TRUE
TRUE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
TRUE
TRUE
TRUE
FALSE
TRUE
FALSE
TRUE
row = 3
row = 4
nクイーン(n-queens)
• この問題を解くためのデータ構造
column 列
row 行
• すでに効き筋 row = 0
→FALSE
row = 1
• queenを置ける
row = 2
→TRUE
row = 3
これを2次元配列で
書いてもよいが、ここでは
次の3つの配列で表現 row = 4
col = 0
col = 1
col = 2
col = 3
col = 4
TRUE
FALSE
TRUE
FALSE
TRUE
FALSE
FALSE
FALSE
TRUE
TRUE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
TRUE
TRUE
TRUE
FALSE
TRUE
FALSE
TRUE
nクイーン(n-queens)
• この問題を解くためのデータ構造
column 列
row 行
配列1:
row = 0
q_row[row]
row = 1
その行にqueenが
いるときにFALSE row = 2
いないときにTRUE
col = 0
col = 1
col = 2
col = 3
col = 4
TRUE
FALSE
TRUE
FALSE
TRUE
FALSE
FALSE
FALSE
TRUE
TRUE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
TRUE
TRUE
TRUE
FALSE
TRUE
FALSE
TRUE
row = 3
row = 4
nクイーン(n-queens)
• この問題を解くためのデータ構造
column 列
row 行
配列2:
row = 0
q_se[col-row+N-1]
row = 1
南東斜め筋は row = 2
col-rowが一定!
col = 0
col = 1
col = 2
col = 3
col = 4
TRUE
FALSE
TRUE
FALSE
TRUE
colrow=-1
FALSE
FALSE
FALSE
TRUE
TRUE
FALSE
colrow=-1
FALSE
FALSE
FALSE
FALSE
FALSE
colrow=-1
FALSE
TRUE
TRUE
TRUE
colrow=-1
FALSE
TRUE
row = 3
FALSE
row = 4
TRUE
FALSE
nクイーン(n-queens)
• この問題を解くためのデータ構造
column 列
row 行
配列3:
q_sw[col+row]
col = 0
col = 1
col = 2
col = 3
col = 4
FALSE
TRUE
col+row
=-3
FALSE
TRUE
FALSE
FALSE
col+row
=-3
FALSE
TRUE
TRUE
FALSE
col+row
=-3
FALSE
FALSE
FALSE
FALSE
col+row
=-3
FALSE
FALSE
FALSE
TRUE
TRUE
TRUE
FALSE
TRUE
FALSE
TRUE
row = 0
TRUE
row = 1
南西斜め筋は row = 2
col+rowが一定!
row = 3
row = 4
nクイーン(n-queens)
• この問題を解くためのデータ構造
column 列
row 行
配列:
q_pos[col]=row
row = 0
row = 1
この配列だけ、 row = 2
前の3つと値が
row = 3
異なることに注意
row = 4
col = 0
col = 1
col = 2
col = 3
col = 4
nクイーン(n-queens)
• バックトラックによる解法
column 列
row 行
配列:
q_pos[col]=row
に、とりあえず
置いてみる。
q_pos[0]=0
row = 0
row = 1
row = 2
row = 3
row = 4
col = 0
col = 1
col = 2
col = 3
col = 4
nクイーン(n-queens)
• バックトラックによる解法
column 列
row 行
配列:
q_pos[col]=row
row = 0
col = 0
col = 1
col = 2
col = 3
col = 4
FALSE
FALSE
FALSE
FALSE
FALSE
row = 1
FALSE
に、とりあえず
置いてみる。
q_pos[0]=0
効き筋を埋める
row = 2
FALSE
row = 3
FALSE
row = 4
FALSE
nクイーン(n-queens)
• バックトラックによる解法
column 列
row 行
配列:
q_pos[col]=row
row = 0
col = 0
col = 1
col = 2
col = 3
col = 4
FALSE
FALSE
FALSE
FALSE
FALSE
row = 1
FALSE
に、とりあえず
置いてみる。
次の候補は
A, B, C
row = 2
row = 3
row = 4
A
B
C
FALSE
FALSE
FALSE
nクイーン(n-queens)
• バックトラックによる解法
column 列
row 行
配列:
q_pos[col]=row
row = 0
col = 0
col = 1
col = 2
col = 3
col = 4
FALSE
FALSE
FALSE
FALSE
FALSE
row = 1
FALSE
とりあえずA
q_pos[1]=2
に置いてみる
row = 2
FALSE
row = 3
FALSE
row = 4
FALSE
nクイーン(n-queens)
• バックトラックによる解法
column 列
row 行
配列:
q_pos[col]=row
とりあえずA
効き筋チェック
row = 0
col = 0
col = 1
col = 2
col = 3
col = 4
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
row = 1
row = 2
row = 3
FALSE
row = 4
FALSE
FALSE
nクイーン(n-queens)
• バックトラックによる解法
column 列
row 行
配列:
q_pos[col]=row
とりあえずA
次の候補はA
row = 0
col = 0
col = 1
col = 2
col = 3
col = 4
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
A
FALSE
row = 1
row = 2
row = 3
FALSE
row = 4
FALSE
nクイーン(n-queens)
• バックトラックによる解法
column 列
row 行
配列:
q_pos[col]=row
とりあえずA
q_pos[2]=4
に置いてみる
row = 0
col = 0
col = 1
col = 2
col = 3
col = 4
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
row = 1
row = 2
row = 3
FALSE
row = 4
FALSE
FALSE
nクイーン(n-queens)
• バックトラックによる解法
column 列
row 行
配列:
q_pos[col]=row
とりあえずA
効き筋チェック
row = 0
col = 0
col = 1
col = 2
col = 3
col = 4
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
row = 1
row = 2
row = 3
row = 4
FALSE
nクイーン(n-queens)
• バックトラックによる解法
column 列
row 行
この場合には
row = 0
うまくいっていますが、
col = 0
col = 1
col = 2
col = 3
col = 4
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
FALSE
row = 1
row = 2
次の候補がなければ
キャンセルして
row = 3
前に戻る
(バックトラック) row = 4
FALSE
nクイーン(n-queens)
• チェスの「クイーン」、n x nの盤面上で、
n個のクイーンがお互いに取らない
(効き筋にならない)ように配置
• 考え方:
– とりあえず、置いてみる。
– 行き詰ったら、前に戻って(バックトラック)、別の選
択肢でやってみる。