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

アルゴリズムとデータ構造
補足資料10-1
「騎士巡回」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
バックトラックアルゴリズム
• とりあえずやってみる
• ダメなら戻って別の道を探る
– あのとき別の道を選んでいたら、、、
• 試行錯誤（trial and error）
– 結局全部のケースをやってみる（完全解）
騎士巡回（knight tour）
• チェスの「ナイト」
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
スタート!
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
2
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
2
3
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
2
3
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
2
3
5
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
6
2
3
5
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
6
2
7
3
5
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
8
6
2
7
3
5
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
8
6
9
2
7
3
5
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
8
6
9
2
7
10
3
5
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
8
6
9
2
7
10
3
5
11
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
8
6
9
2
7
10
3
5
12
11
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1
8
6
9
2
13
7
10
3
5
12
11
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1 14
8
6
9
2
13
7
10
3
5
12
11
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1 14
8
6
9
15
10
2
13
7
3
5
12
11
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1 14
8
6
9
15
10
2
13
7
3
5
16 11
12
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1 14
8
6
9
15
10
2
13
7
3
5
17 12
16 11
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1 14
8
6
9
15
10
2
13 18
7
3
5
17 12
16 11
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1 14 19 8
6
9
15
10
2
13 18
7
3
5
17 12
16 11
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1 14 19 8
6
9
2
13 18
15 20
7
3
10
5
17 12
16 11
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1 14 19 8
6
9
2
13 18
15 20
7
3
10
5
21 16 11
17 12
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1 14 19 8
6
9
2
13 18
15 20
7
3
10
22 17 12
5
21 16 11
4
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1 14 19 8
6
9
2
13 18
15 20
7
3
10
22 17 12
5
21 16 11
4
23
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
1 14 19 8
6
9
2
13 18
15 20
7
24
10
22 17 12
5
21 16 11
4
3
23
ゴール!
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
• 考え方：
– とりあえず、行けるところまで行ってみる。
– 行き詰ったら、前に戻って（バックトラック）、別の選
択肢でやってみる。
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
戻ってやりなおす。
スタート!
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
戻ってやりなおす。
A
B
ここで人生の
分かれ道：
A～Bのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
戻ってやりなおす。
A
B
ここで人生の
分かれ道：
A～Bのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
E
戻ってやりなおす。
D
A
C
B
ここで人生の
分かれ道：
A～Eのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
E
戻ってやりなおす。
D
A
C
B
ここで人生の
分かれ道：
A～Eのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
2
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
C
戻ってやりなおす。
2
ここで人生の
分かれ道：
B
A
A～Cのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
C
戻ってやりなおす。
2
ここで人生の
分かれ道：
B
A
A～Cのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
2
3
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
2
B
A
3
ここで人生の
分かれ道：
A～Bのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
2
B
A
3
ここで人生の
分かれ道：
A～Bのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
2
3
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
A
2
B
4
3
A～Bのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
A
2
B
4
3
A～Bのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
2
3
5
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
B
戻ってやりなおす。
2
A
3
5
4
A～Bのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
B
戻ってやりなおす。
2
A
3
5
4
A～Bのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
2
3
5
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1 D
E
戻ってやりなおす。
6
2
F
3
C
5
B
A
4
A～Fのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1 D
E
戻ってやりなおす。
6
2
F
3
C
5
B
A
4
A～Fのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
2
7
3
5
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
2
B
7
3
5
A
4
A～Bのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
2
B
7
3
5
A
4
A～Bのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
2
7
3
5
8
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
2
B
A
7
C
5
3
8
4
A～Cのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
2
B
A
7
C
5
3
8
4
A～Cのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
2
7
3
5
8
9
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
2
7
10
3
5
8
9
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
C
戻ってやりなおす。
6
2
7
10
5
A
B
9
3
8
4
A～Cのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
C
戻ってやりなおす。
6
2
7
10
5
A
B
9
3
8
4
A～Cのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
7
10
3
5
8
9
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
B
C
戻ってやりなおす。
6
11
2
7
10
3
5
8
9
4
A
A～Cのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
B
C
戻ってやりなおす。
6
11
2
7
10
3
5
8
9
4
A
A～Cのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
7
10
12
5
3
8
9
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
7
10
12
5
3
8
9
4
13
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
B
10
A
2
C
7
12
5
3
8
9
4
13
A～Cのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
B
10
A
2
C
7
12
5
3
8
9
4
13
A～Cのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
7
10
5
12
14
9
3
8
4
13
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
7
10
15
5
12
14
9
3
8
4
13
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
B
戻ってやりなおす。
6
10
15
11
5
2
C
7
12
3
14
A
8
9
4
13
A～Cのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
B
戻ってやりなおす。
6
10
15
11
5
2
C
7
12
3
14
A
8
9
4
13
A～Cのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
10
15
11
2
16
7
5
14
9
12
3
8
4
13
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
16
7
10
5
14
15
A
9
B
12
3
8
4
13
A～Bのどれを
選ぶ？
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
16
7
10
5
14
15
A
9
B
12
3
8
4
13
A～Bのどれを
選ぶ？
とりあえずA
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
10
15
11
2
16
7
12
3
5
14 17
8
9
13
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
10
11
2
16
7
12
3
5
14 17
8
9
13
15 18
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
19 16
7
12
3
10
14 17
8
9
13
5
15 18
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1 20
戻ってやりなおす。
6
11
2
19 16
7
12
3
10
14 17
8
9
13
5
15 18
手詰まり!!!!!
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1 20
戻ってやりなおす。
6
11
2
19 16
7
12
3
10
14 17
8
9
13
5
15 18
手詰まり!!!!!
4
ダメな時は
前の選択肢まで
戻ってやり直す
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
19 16
7
12
3
10
14 17
8
9
13
5
15 18
手詰まり!!!!!
4
ダメな時は
前の選択肢まで
戻ってやり直す
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
10
11
2
16
7
12
3
5
14 17
8
9
13
15 18
手詰まり!!!!!
4
ダメな時は
前の選択肢まで
戻ってやり直す
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
10
15
11
2
16
7
12
3
5
14 17
8
9
13
手詰まり!!!!!
4
ダメな時は
前の選択肢まで
戻ってやり直す
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
16
7
10
5
14
15
A
9
B
12
3
8
4
13
A～Bのどれを
選ぶ？
Aは失敗だった。
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
16
7
10
5
14
15
A
9
B
12
3
8
4
13
A～Bのどれを
選ぶ？
Aは失敗だった。
じゃあB
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
10
15
11
2
16
7
12
3
5
14 17
8
9
13
4
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
10
15
11
2
18
16
7
12
3
5
14 17
8
9
13
4
手詰まり!!!!!
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
10
15
11
2
16
7
12
3
5
14 17
8
9
13
手詰まり!!!!!
4
ダメな時は
前の選択肢まで
戻ってやり直す
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
16
7
10
5
14
15
A
9
B
12
3
8
4
13
A～Bのどれを
選ぶ？
Aは失敗だった。
Bも失敗だった。
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
16
7
10
5
14
15
A
9
B
12
3
8
4
13
すべての
選択肢がダメ
ダメな時は
前の選択肢まで
戻ってやり直す
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
B
戻ってやりなおす。
6
10
15
11
5
2
C
7
12
3
14
A
8
9
4
13
A～Cのどれを
選ぶ？
Aは失敗だった。
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
B
戻ってやりなおす。
6
10
15
11
5
2
C
7
12
3
14
A
8
9
4
13
A～Cのどれを
選ぶ？
Aは失敗だった。
じゃあB
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
10
15
11
2
16
7
5
14
9
12
3
8
4
13
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1 22 17
戻ってやりなおす。
6 11 2 23 18 Bもダメ！
21 16
7
12
3
10
14 19
8
9
13
5
15 20
4
人生試行錯誤。
あきらめずに
がんばれ！
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
B
戻ってやりなおす。
6
10
15
11
5
2
C
7
12
3
14
A
8
9
4
13
A～Cのどれを
選ぶ？
Aは失敗だった。
Bは失敗だった。
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
B
戻ってやりなおす。
6
10
15
11
5
2
C
7
12
3
14
A
8
9
4
13
A～Cのどれを
選ぶ？
Aは失敗だった。
Bは失敗だった。
じゃあC
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1 18 23
戻ってやりなおす。
6 11 2 17 22 Cもダメ！
19 16
7
12
3
10
14 21
8
9
13
5
15 20
4
人生試行錯誤。
あきらめずに
がんばれ！
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
B
戻ってやりなおす。
6
10
15
11
5
2
C
7
12
3
14
A
8
9
4
13
A～Cのどれを
選ぶ？
Aは失敗だった。
Bは失敗だった。
Cは失敗だった。
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
2
7
10
5
12
14
9
3
8
4
13
ダメな時は
あきらめずに
前の選択肢まで
戻ってやり直す
騎士巡回（knight tour）
• 分かれ道は、とりあえず進んでみる。
ダメな時は
1
戻ってやりなおす。
6
11
B
10
A
2
C
7
12
5
3
8
9
4
13
A～Cのどれを
選ぶ？
Aは失敗だった
じゃあ、
Bいっときますか
騎士巡回（knight tour）
• さっき見せたのは正解（の一つ）
1
14 19
8
6
9
2
13 18
15 20
7
24
10
22 17 12
5
21 16 11
4
3
23
試行回数
（移動回数）は
8,839回！
騎士巡回（knight tour）
• チェスの「ナイト」、盤面のすべてのマスを
一度だけ訪問する
• 考え方：
– とりあえず、行けるところまで行ってみる。
– 行き詰ったら、前に戻って（バックトラック）、別の選
択肢でやってみる。
騎士巡回（knight tour）
A
B
選択肢
試行
A
やり直し
（バックトラック）
B
1
E
D
A
C
A
1
B
E
BC D
C
2
B
…
1
6
10
A
5
2
C
7
12
3
14
A
8
9
4
13
B
失敗
失敗
C
失敗
1
6
A
失敗
11
2
16
7
10
5
14
15
A
9
B
12
失敗
3
失敗
失敗
…
失敗
ゴール！
1
8
4
…
C
B
B
11
15
A
A
失敗
13
B
失敗
失敗
失敗
14
19
8
6
9
2
13
15
20
7
24
18
3
10
5
22
17
12
21
16
11
4
23
バックトラック（モデル）
A
B
選択肢
試行
A
やり直し
（バックトラック）
B
1
E
D
A
C
A
1
B
E
BC D
C
2
B
…
1
6
10
A
5
2
C
7
12
3
14
A
8
9
4
13
B
失敗
失敗
C
失敗
1
6
A
失敗
11
2
16
7
10
5
14
15
A
9
B
12
失敗
3
失敗
失敗
…
失敗
ゴール！
1
8
4
…
C
B
B
11
15
A
A
失敗
13
B
失敗
失敗
失敗
14
19
8
6
9
2
13
15
20
7
24
18
3
10
5
22
17
12
21
16
11
4
23

Download Report