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