【アルゴリズム】 騎士巡歴の問題

騎士巡歴の問題

騎士（ナイト）は桂馬の動きと同じような動きを上下左右に行える。このとき、与えられたますにすべて訪れるにはどのようなルートをたどればよいかを調べる。

Rubyでそのまんま書いたらこんな感じになった。

N = 5

$board = Array.new(N + 4){ Array.new(N + 4) }
$dx = [2, 1, -1, -2, -2, -1, 1, 2]
$dy = [1, 2, 2, 1, -1, -2, -2, -1]

$count = 0
$solution = 0

def printboard
  printf "解 %d\\n", $solution += 1

  (2..N + 1).each do |i|
    (2..N + 1).each do |j|
      printf "%4d", $board[i][j]
    end

    puts ""
  end

  puts ""
end

def tryVisit(x, y)
  return unless $board[x][y] == 0
  $count += 1
  $board[x][y] = $count

  if $count == N * N
    printboard 
  else
    8.times do |i|
      tryVisit(x + $dx[i], y + $dy[i])
    end
  end

  $board[x][y] = 0
  $count -= 1
end

def main
  (0..N + 3).each do |i|
    (0..N + 3).each do |j|
      $board[i][j] = 1
    end
  end

  (2..N + 1).each do |i|
    (2..N + 1).each do |j|
      $board[i][j] = 0
    end
  end

  tryVisit(2, 2)
  return 0
end

main

実行結果は以下のようになった。

解 1
   1   6  15  10  21
  14   9  20   5  16
  19   2   7  22  11
   8  13  24  17   4
  25  18   3  12  23

解 2
   1   6  11  18  21
  12  17  20   5  10
   7   2  15  22  19
  16  13  24   9   4
  25   8   3  14  23

解 3
   1   6  11  16  21
  12  15  20   5  10
   7   2  13  22  17
  14  19  24   9   4
  25   8   3  18  23

解 4
   1   6  17  12  21
  16  11  20   5  18
   7   2   9  22  13
  10  15  24  19   4
  25   8   3  14  23

～～～～ 省略 ～～～～

解 301
   1  14  19   8  25
   4   9   2  13  18
  15  20   5  24   7
  10   3  22  17  12
  21  16  11   6  23

解 302
   1  16   5  10  25
   4  11   2  15   6
  17  20   7  24   9
  12   3  22  19  14
  21  18  13   8  23

解 303
   1  10   5  14  25
   4  15   2  19   6
   9  20  11  24  13
  16   3  22   7  18
  21   8  17  12  23

解 304
   1  10   5  16  25
   4  17   2  11   6
   9  20  13  24  15
  18   3  22   7  12
  21   8  19  14  23

これは、解がひとつ解けたら一つ前のマスに戻って他の経路が無いかを調べる。あったらそのマスを探ればいいし、無かったらまた1段階下げていく。そうすると最終的にすべての経路が洗い出せる、というのがこのアルゴリズムのようだ。

実は、解をひとつ解く過程において、当然行き詰まりなどもある。試しに30行目あたりにprintboard関数をはさむと、解1がでるまでに8840個ほどの経路を調査している。行き詰まって大量にやり直ししている様子が伺える。

それでも、きちんと戻ってやり直ししてゴールにまでたどり着き、すべてのマスに辿りつけられる経路を調査し、終わったら終了できるのはすごいなぁと思ってしまうわけです。

自力だったら、うまく行ってもっと複雑なコードになっているか、普通に頓挫するでしょうね。。もっと勉強が必要だ。

2012/08/04 7:18