「騎士の巡歴」とは、チェスの「騎士（ナイト）」の駒を使って、チェス盤のマスを一度づつ移動していき、最終的にすべてのマスを訪れるというパズルです。「騎士」の駒は将棋の「桂馬」とよく似た動きをしますが、すべての方向に飛べるだけ桂馬とちがいます。
Ruby で解いてみました。しかし、実際のチェス盤の大きさである 8×8 では、盤が大きすぎて解を求めることができませんでした。以下のコードでは（左上隅を出発点とする）すべての解を出力しますが、6×5 の盤面（解は4542通り）くらいが限界のようです。実行例。
$ time ruby tour_of_knight.rb （省略） ----------------------- No. 4540 01 04 21 08 15 06 22 13 02 05 26 09 03 20 27 14 07 16 12 23 18 29 10 25 19 28 11 24 17 30 ----------------------- No. 4541 01 04 21 08 15 06 26 09 02 05 22 13 03 20 27 14 07 16 10 25 18 29 12 23 19 28 11 24 17 30 ----------------------- No. 4542 01 04 21 08 15 06 22 09 02 05 26 13 03 20 27 14 07 16 10 23 18 29 12 25 19 28 11 24 17 30 real 2m32.799s user 2m32.652s sys 0m0.112s
Ruby コード。
tour_of_knight.rb
X, Y = 6, 5 jump = [[-1, 2], [1, 2], [-1, -2], [1, -2], [2, -1], [2, 1], [-2, -1], [-2, 1]] a = Array.new(X + 4, -1) board = [a] * 2 + Array.new(Y) {[-1] * 2 + [0] * X + [-1] * 2} + [a] * 2 co = 1 try = ->(x, y, n) { if n == X * Y puts "-----------------------" puts "No. #{co}" board[2, Y].each {|a| puts a[2, X].map{|b| "%02d " % b}.join} co += 1 else jump.each do |right, down| x1, y1 = x + right, y + down next if board[y1][x1].nonzero? board[y1][x1] = n + 1 try.(x1, y1, n + 1) board[y1][x1] = 0 end end } board[2][2] = 1 try.(2, 2, 1)
ふつうのバックトラック法で求めています。変数 jump には「騎士」の相対的な移動可能方向が入っています。変数 board は盤面です。周囲には番兵（-1）が置いてあって盤外かどうかをチェックしています。
なおここによると、「騎士の巡歴」を解くのに「ワーンスドロフの規則」というのがあって、このアルゴリズムを使うととても高速に解けるらしいのだが、その規則によって確実に解けるということはまだ証明されていないらしい。検索してみても「ワーンスドロフの規則」を使ったものは多いが、証明がないということでここでは採用しなかった。また、自分で考えたアルゴリズムでもないしね。
