読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

数学パズル本に敢てプログラムで挑戦(2)

いったん書くとこれがなかなか面白いのがblogの中毒的な所、というわけで今日も昨日の続きでAlgorithmic Puzzlesを解いていこう。

45. A Knight’s Shortest Path(ナイトの最短路)

100*100のチェスボード上の左下コーナーにナイトが居る時、右上のコーナーへは最短何手で行けるか?

最短路とあるけれど、ダイクストラアルゴリズムは必要ない。というのも、全ての一手の価値は同じだから幅優先探索でOK。つまり、最初の位置から一手で進める場所を調べて、そこから更に一手で進める場所を・・・というのを、ゴールに辿り着くまで||進める場所がなくなるまで、行う。もちろん同じ場所を何度も行こうとするから、visitedというハッシュにそのマスまでの最短手数を入れてフラグとする。 直感的にはナイトのジャンプはイビツだからうまくたどり着けない可能性やゴール直前で調整する手数が必要かなと思う。

#!ruby

#45. A Knight’s Shortest Path
#What is the minimum number of moves needed for a chess knight
#to go from one corner of a 100 × 100 board to the diagonally opposite corner?

N = 100

def is_pos_regitimate?(x, y)
    ((0...N) === x) && ((0...N) === y)
end

Moves = [
                    [ 1, 2],
                    [-1, 2],
                    [ 1,-2],
                    [-1,-2],
                    [ 2, 1],
                    [-2, 1],
                    [ 2,-1],
                    [-2,-1]
                ]
Init_Pos = [    0,     0]
Goal_Pos = [N - 1, N - 1]

queue = Array.new
queue.push [Init_Pos, 0]
visited = Array.new(N){Array.new(N)}

until visited.dig(*Goal_Pos) || queue.empty?
    pos, move_num = queue.shift
    next if visited.dig(*pos)
    x, y = pos
    visited[x][y] = move_num
    Moves.each{|dx, dy|
        next_pos = [x + dx, y + dy]
        if is_pos_regitimate?(*next_pos)
            queue.push [next_pos, move_num + 1] unless visited.dig(*next_pos)
        end
    }
end

puts visited.dig(*Goal_Pos) || "Impossible!"

ここでは新しく覚えたdigメソッドを使ってみた。多重構造の時にコード数を減らせるし、今回のように*展開で配列も渡せて美味しい。結果は66というなんとなく納得できる数字に。というのもナイトの動きって1行って2行くわけだから、2回動けば対角線に(3,3)に行ける。従って、(100,100)に行くには66回動けばいいでしょうという寸法。他のNでも同じ結果に。N=2のときだけ解がないようだ。

   N | answer
-----------
  10 | 6
 100 | 66
1000 | 666