交差せずに一筆書き（Ruby）

問題：
長方形状に横 5 個、縦 4 個の格子点が全部で 20個、等間隔に並んでいます。このすべての格子点を一筆書き（交差してはならない）で辿るとすると、その辿り方は全部で何とおりあるでしょうか。
ただし進む方向は上下左右のみで、また始点と終点が反対になっているだけで同じパターンは除外することにします。

　
Ruby で解いてみます。
q62.rb

m, n = 5, 4
count = 0

solve = ->(x, y, history) {
  if history.size == m * n
    count += 1
  else
    [[1, 0], [-1, 0], [0, 1], [0, -1]].each do |dir|
      x1, y1 = x + dir[0], y + dir[1]
      next if x1 < 0 or x1 >= m or y1 < 0 or y1 >= n or history.include?([x1, y1])
      solve.(x1, y1, history + [[x1, y1]])
    end
  end
}

m.times do |x|
  n.times {|y| solve.(x, y, [[x, y]])}
end
puts count / 2

結果。

$ time ruby q62.rb
1006

real	0m2.004s
user	0m1.992s
sys	0m0.012s

単純な深さ優先探索で求めています。ひとつのパターンに付き始点と終点を入れ替えたものが存在するので、最後に結果を半分にします。
　

別解（9/27）

上のコードは配列 history の処理が重いので、多少改変してみました。
q62b.rb

m, n = 5, 4
count = 0
field = Array.new(n) {Array.new(m, 0)}

solve = ->(x, y, num) {
  field[y][x] = 1
  if num == m * n
    count += 1
  else
    [[1, 0], [-1, 0], [0, 1], [0, -1]].each do |dir|
      x1, y1 = x + dir[0], y + dir[1]
      next if x1 < 0 or x1 >= m or y1 < 0 or y1 >= n or field[y1][x1].nonzero?
      solve.(x1, y1, num + 1)
    end
  end
  field[y][x] = 0
}

m.times do |x|
  n.times {|y| solve.(x, y, 1)}
end
puts count / 2

これだと結果はこうなります。

$ time ruby q62b.rb
1006

real	0m0.468s
user	0m0.464s
sys	0m0.004s

およそ 4.3倍高速化しています。
　

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問