https://qiita.com/Nabetani/items/7baf181b4a1b7eacc79a

doukaku20.rb

MAZE = {
  "0" => %w[1 6],
  "1" => %w[0 7],
  "2" => %w[3],
  "3" => %w[2 4 9],
  "4" => %w[3 5],
  "5" => %w[4 B],
  "6" => %w[0 C],
  "7" => %w[1 8],
  "8" => %w[7 9],
  "9" => %w[3 8 A F],
  "A" => %w[9],
  "B" => %w[5],
  "C" => %w[6 D I],
  "D" => %w[C],
  "E" => %w[K],
  "F" => %w[9 G],
  "G" => %w[F M],
  "H" => %w[N],
  "I" => %w[C O],
  "J" => %w[K P],
  "K" => %w[E J L],
  "L" => %w[K M],
  "M" => %w[G L S],
  "N" => %w[H T],
  "O" => %w[I],
  "P" => %w[J Q V],
  "Q" => %w[P R],
  "R" => %w[Q X],
  "S" => %w[M T Y],
  "T" => %w[N S],
  "U" => %w[V],
  "V" => %w[P U W],
  "W" => %w[V],
  "X" => %w[R],
  "Y" => %w[S Z],
  "Z" => %w[Y],
}

def traverse(now, goal, route = now)
  MAZE[now].map do |nxt|
    if nxt == goal  # ゴールに着いた
      route.length + 1
    elsif route.include?(nxt)  # ここもう通ったよ？
      999
    else  # まだ道半ば
      traverse(nxt, goal, route + nxt)
    end
  end.min
end

def test(input, expect)
  now, goal = input.split(//)
  result = traverse(now, goal) - 1  # 1引くのは開始地点の分を含んでいるため
  if result != expect.to_i
    raise "'#{input}' expects #{expect}, but returned #{result}"
  end
end

test( "DE", "13" );
test( "EK", "1" );
test( "01", "1" );
test( "LG", "2" );
test( "A1", "4" );
test( "GJ", "4" );
test( "FK", "4" );
test( "LV", "4" );
test( "27", "4" );
test( "0O", "4" );
test( "G1", "5" );
test( "ZH", "5" );
test( "AB", "5" );
test( "KX", "5" );
test( "1G", "5" );
test( "WX", "5" );
test( "3L", "5" );
test( "9Y", "5" );
test( "EX", "6" );
test( "BG", "6" );
test( "7K", "7" );
test( "E3", "7" );
test( "SW", "7" );
test( "BM", "7" );
test( "3C", "7" );
test( "H9", "7" );
test( "J3", "7" );
test( "GX", "8" );
test( "2Z", "8" );
test( "8H", "8" );
test( "Z7", "8" );
test( "0B", "8" );
test( "U9", "9" );
test( "Z0", "10" );
test( "0N", "10" );
test( "U8", "10" );
test( "XZ", "10" );
test( "H0", "11" );
test( "CH", "13" );
test( "WB", "13" );
test( "0R", "13" );
test( "DZ", "13" );
test( "NI", "13" );
test( "QC", "14" );
test( "6U", "14" );
test( "PO", "15" );
test( "RI", "16" );
test( "UO", "17" );
test( "WO", "17" );
test( "OX", "18" );