■

次の課題は、『騎士の旅行の問題』。
大昔（1983年）に買った『ソフトウェア設計』（共立出版）に載っているやつ。バックトラッキングでやると10分以上かけて失敗したそうだけど、今のPCなら（この本の著者はIBMのメインフレームでPL/Iでやったとのこと）、素直にやっても何とかなるんじゃないだろうか？
問題は、チェス盤の上から4行目、右から4列目にナイト（knight）をおいて、ナイトが動ける場所に順に進んで、盤上のすべてのますを通ることができるか、という問題。
残念ながら、素朴なバックトラッキング・アルゴリズムでは、20分以上かけても、解を得ることができず、実行を中断した。6x6ならすぐに（0.3秒で）解は出たが。
はじめのうちは、次に進める場所の候補は、見つけやすいが、後になるほど候補が少なくなるので、それなりに処理が進まないと失敗がわからない。そんなわけで、なかなか解が見つからないようだ。問題の性質上、CPUパワーが大きくなったからといって、そう簡単には行かないらしい。