アルゴリズムとデータ構造 補足資料10-1 「騎士巡回」 横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

バックトラックアルゴリズム とりあえずやってみる ダメなら戻って別の道を探る 試行錯誤（trial and error） あのとき別の道を選んでいたら、、、 試行錯誤（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 3 10 5 4

騎士巡回（knight tour） 1 8 6 9 2 7 3 10 5 11 4 チェスの「ナイト」、盤面のすべてのマスを 　　　　　　　　　　　　　　　　　　　一度だけ訪問する 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 チェスの「ナイト」、盤面のすべてのマスを 　　　　　　　　　　　　　　　　　　　一度だけ訪問する 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 チェスの「ナイト」、盤面のすべてのマスを 　　　　　　　　　　　　　　　　　　　一度だけ訪問する 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 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 ここで人生の 分かれ道： 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 A B ここで人生の 分かれ道： A～Bのどれを 選ぶ？

騎士巡回（knight tour） A B 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 ここで人生の 分かれ道： 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 A B ここで人生の 分かれ道： A～Bのどれを 選ぶ？ とりあえずA

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1

騎士巡回（knight tour） 1 E D A C B 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 ここで人生の 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 E D A C B ここで人生の 分かれ道： A～Eのどれを 選ぶ？

騎士巡回（knight tour） 1 E D A C B 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 ここで人生の 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 E D A C B ここで人生の 分かれ道： A～Eのどれを 選ぶ？ とりあえずA

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 2

騎士巡回（knight tour） 1 C 2 B A 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 ここで人生の 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 C 2 B A ここで人生の 分かれ道： A～Cのどれを 選ぶ？

騎士巡回（knight tour） 1 C 2 B A 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 ここで人生の 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 C 2 B A ここで人生の 分かれ道： A～Cのどれを 選ぶ？ とりあえずA

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 2 3

騎士巡回（knight tour） 1 2 B 3 A 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 ここで人生の 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 2 B 3 A ここで人生の 分かれ道： A～Bのどれを 選ぶ？

騎士巡回（knight tour） 1 2 B 3 A 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 ここで人生の 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 2 B 3 A ここで人生の 分かれ道： A～Bのどれを 選ぶ？ とりあえずA

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 2 3 4

騎士巡回（knight tour） 1 A 2 B 3 4 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 A 2 B 3 4 A～Bのどれを 選ぶ？

騎士巡回（knight tour） 1 A 2 B 3 4 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 A 2 B 3 4 A～Bのどれを 選ぶ？ とりあえずA

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 2 3 5 4

騎士巡回（knight tour） 1 B 2 A 3 5 4 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 B 2 A 3 5 4 A～Bのどれを 選ぶ？

騎士巡回（knight tour） 1 B 2 A 3 5 4 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 A B 4 分かれ道は、とりあえず進んでみる。 ダメな時は 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 D E 6 2 F 3 C 5 A B 4 A～Fのどれを 選ぶ？

騎士巡回（knight tour） 1 D E 6 2 F 3 C 5 A B 4 分かれ道は、とりあえず進んでみる。 ダメな時は 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 D E 6 2 F 3 C 5 A B 4 A～Fのどれを 選ぶ？ とりあえずA

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 6 2 7 3 5 4

騎士巡回（knight tour） 1 6 2 B 7 3 5 A 4 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 6 2 B 7 3 5 A 4 A～Bのどれを 選ぶ？

騎士巡回（knight tour） 1 6 2 B 7 3 5 A 4 分かれ道は、とりあえず進んでみる。 ダメな時は 戻ってやりなおす。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 7 C 3 A 5 8 4 分かれ道は、とりあえず進んでみる。 ダメな時は 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 6 2 B 7 C 3 A 5 8 4 A～Cのどれを 選ぶ？

騎士巡回（knight tour） 1 6 2 B 7 C 3 A 5 8 4 分かれ道は、とりあえず進んでみる。 ダメな時は 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 6 2 B 7 C 3 A 5 8 4 A～Cのどれを 選ぶ？ とりあえずA

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 6 2 7 3 5 8 9 4

騎士巡回（knight tour） 1 6 2 7 3 10 5 8 9 4 分かれ道は、とりあえず進んでみる。 ダメな時は 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 分かれ道は、とりあえず進んでみる。 ダメな時は 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 C 6 2 7 A 3 10 5 B 8 9 4 A～Cのどれを 選ぶ？

騎士巡回（knight tour） 1 C 6 2 7 A 3 10 5 B 8 9 4 分かれ道は、とりあえず進んでみる。 ダメな時は 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 C 6 2 7 A 3 10 5 B 8 9 4 A～Cのどれを 選ぶ？ とりあえずA

騎士巡回（knight tour） 1 6 11 2 7 3 10 5 8 9 4 分かれ道は、とりあえず進んでみる。 ダメな時は 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 B C 6 11 2 7 3 10 5 8 9 4 A A～Cのどれを 選ぶ？

騎士巡回（knight tour） 1 B C 6 11 2 7 3 10 5 8 9 4 A 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 B C 6 11 2 7 3 10 5 8 9 4 A A～Cのどれを 選ぶ？ とりあえずA

騎士巡回（knight tour） 1 6 11 2 7 12 3 10 5 8 9 4 分かれ道は、とりあえず進んでみる。 ダメな時は 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 A～Cのどれを 選ぶ？

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 6 11 2 C B 7 12 3 10 5 8 A 9 4 13 A～Cのどれを 選ぶ？ とりあえずA

騎士巡回（knight tour） 1 6 11 2 7 12 3 10 5 14 8 9 4 13 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 A～Cのどれを 選ぶ？

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 B 6 11 2 C 7 12 3 10 5 14 A 8 15 9 4 13 A～Cのどれを 選ぶ？ とりあえずA

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 A～Bのどれを 選ぶ？

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 6 11 2 B 16 7 12 3 10 5 14 8 15 A 9 4 13 A～Bのどれを 選ぶ？ とりあえずA

騎士巡回（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 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 A～Bのどれを 選ぶ？ Aは失敗だった。

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 6 11 2 B 16 7 12 3 10 5 14 8 15 A 9 4 13 A～Bのどれを 選ぶ？ Aは失敗だった。 じゃあB

騎士巡回（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 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 A～Bのどれを 選ぶ？ Aは失敗だった。 Bも失敗だった。

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 A～Cのどれを 選ぶ？ Aは失敗だった。

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 B 6 11 2 C 7 12 3 10 5 14 A 8 15 9 4 13 A～Cのどれを 選ぶ？ Aは失敗だった。 じゃあB

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 A～Cのどれを 選ぶ？ Aは失敗だった。 Bは失敗だった。

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 1 B 6 11 2 C 7 12 3 10 5 14 A 8 15 9 4 13 A～Cのどれを 選ぶ？ Aは失敗だった。 Bは失敗だった。 じゃあC

騎士巡回（knight tour） 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 A～Cのどれを 選ぶ？ Aは失敗だった。 Bは失敗だった。 Cは失敗だった。

騎士巡回（knight tour） 1 6 11 2 7 12 3 10 5 14 8 9 4 13 分かれ道は、とりあえず進んでみる。 　　　　　　　　　　　　　　　　　　　ダメな時は 　　　　　　　　　　　　　　　　　　　戻ってやりなおす。 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 A～Cのどれを 選ぶ？ Aは失敗だった じゃあ、 Bいっときますか

騎士巡回（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 試行回数 （移動回数）は 8,839回！

騎士巡回（knight tour） チェスの「ナイト」、盤面のすべてのマスを 一度だけ訪問する 考え方： 　　　　　　　　　　　　　　　　　　　一度だけ訪問する 考え方： とりあえず、行けるところまで行ってみる。 行き詰ったら、前に戻って（バックトラック）、別の選択肢でやってみる。

騎士巡回（knight tour） ゴール！ 選択肢 試行 A B やり直し （バックトラック） E A B C D … A C B … 1 E D A C B E A B C D 1 C 2 B A … A C B … 失敗 1 B 6 11 2 C 7 12 3 10 5 14 A 8 15 9 4 13 失敗 A C B 失敗 1 6 11 2 B 16 7 12 3 10 5 14 8 15 A 9 4 13 失敗 失敗 失敗 ゴール！ 失敗 … 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 やり直し （バックトラック） E A B C D … A C B … 失敗 失敗 1 E D A C B E A B C D 1 C 2 B A … A C B … 失敗 1 B 6 11 2 C 7 12 3 10 5 14 A 8 15 9 4 13 失敗 A C B 失敗 1 6 11 2 B 16 7 12 3 10 5 14 8 15 A 9 4 13 失敗 失敗 失敗 ゴール！ 失敗 … 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 失敗 失敗 失敗