ふたたび Ruby で 8 queen（関数型プログラミングっぽく）

ここで Ruby で「8 クイーン問題」を解いてみましたが、関数型プログラミングのお勉強に Common Lisp のコード例を移植してみました。

参考にしたのはこのサイトです。

実行するとこんな感じです。

----------
No.1
...@....
.@......
......@.
..@.....
.....@..
.......@
....@...
@.......
----------
No.2
....@...
.@......
...@....
......@.
..@.....
.......@
.....@..
@.......
----------
...

全部で解は92通りあります。

コード。

class Array
  def car; first;   end
  def cdr; drop(1); end
end

attack = ->(x, xs) {
  attack_sub = ->(n, ys) {
    if ys.empty?
      true
    elsif ys.car + n == x or ys.car - n == x
      false
    else
      attack_sub[1 + n, ys.cdr]
    end
  }
  attack_sub[1, xs]
}

safe = ->(ls) {
  if ls.empty?
    true
  elsif attack[ls.car, ls.cdr]
    safe[ls.cdr]
  else
    false
  end
}

counter = 0

print = ->(board) {
  puts "-" * 10
  puts "No.#{counter += 1}"
  board.each do |po|
    st = "." * board.size
    st[po - 1] = "@"
    puts st
  end
}

queen = ->(nums, board) {
  if nums.empty?
    print[board] if safe[board]
  else
    nums.each do |x|
      queen[nums - [x], [x] + board]
    end
  end
}

iota = ->(n) {
  (n == 1) ? [1] : iota[n - 1] + [n]
}

queen[iota[8], []]

高速化版です。

queen_fast = ->(nums, board) {
  if nums.empty?
    print[board]
  else
    nums.each do |x|
      queen_fast[nums - [x], [x] + board] if attack[x, board]
    end
  end
}

queen_fast[iota[8], []]

Common Lisp 版のほぼ忠実な移植で、しかもずっと読みやすくなっていると思います。このような形の関数型プログラミングなら、Ruby で充分可能だということがわかります。
　
かかった時間です。最初のバージョン。

real	0m0.313s
user	0m0.276s
sys	0m0.004s

高速化されたバージョン。

real	0m0.091s
user	0m0.048s
sys	0m0.012s

6倍くらい高速化されていますね。