8queen問題

Ruby puzzle

http://ja.wikipedia.org/wiki/エイト・クイーン

すげー悩んだけどわりと綺麗にできた。
再帰+lambda渡しは再帰を巻き戻さないで良いので書きやすい。
変な書き方しないようにしたけど20行きった。

#!/usr/bin/env ruby
def put(size=8, queens=[], &block)
  block.call(queens) if block and queens.size >= size
  (queens.empty? ? 1 : queens.last[:x]).upto(size).each do |x|
    1.upto(size).each do |y|
      q = {:x => x, :y => y}
      next if queens.map{|i|
        q[:x] == i[:x] or q[:y] == i[:y] or q[:x]+q[:y] == i[:x]+i[:y] or q[:x]-q[:y] == i[:x]-i[:y] 
      }.include? true
      queens_ = queens.clone
      queens_.push q
      put(size, queens_, &block)
    end
  end
end

put(ARGV.empty? ? 8 : ARGV.shift.to_i){|queens|
  puts queens.map{|q| "[#{q[:x]},#{q[:y]}]"}.join('')
}


結果。queenを置くべき座標のリストがでてくる。全92通り。

[1,1][2,5][3,8][4,6][5,3][6,7][7,2][8,4]
[1,1][2,6][3,8][4,3][5,7][6,4][7,2][8,5]
[1,1][2,7][3,4][4,6][5,8][6,2][7,5][8,3]
[1,1][2,7][3,5][4,8][5,2][6,4][7,6][8,3]
[1,2][2,4][3,6][4,8][5,3][6,1][7,7][8,5]
[1,2][2,5][3,7][4,1][5,3][6,8][7,6][8,4]
[1,2][2,5][3,7][4,4][5,1][6,8][7,6][8,3]
[1,2][2,6][3,1][4,7][5,4][6,8][7,3][8,5]
[1,2][2,6][3,8][4,3][5,1][6,4][7,7][8,5]
[1,2][2,7][3,3][4,6][5,8][6,5][7,1][8,4]
[1,2][2,7][3,5][4,8][5,1][6,4][7,6][8,3]
[1,2][2,8][3,6][4,1][5,3][6,5][7,7][8,4]
[1,3][2,1][3,7][4,5][5,8][6,2][7,4][8,6]
[1,3][2,5][3,2][4,8][5,1][6,7][7,4][8,6]
[1,3][2,5][3,2][4,8][5,6][6,4][7,7][8,1]
[1,3][2,5][3,7][4,1][5,4][6,2][7,8][8,6]
[1,3][2,5][3,8][4,4][5,1][6,7][7,2][8,6]
[1,3][2,6][3,2][4,5][5,8][6,1][7,7][8,4]
[1,3][2,6][3,2][4,7][5,1][6,4][7,8][8,5]
[1,3][2,6][3,2][4,7][5,5][6,1][7,8][8,4]
[1,3][2,6][3,4][4,1][5,8][6,5][7,7][8,2]
[1,3][2,6][3,4][4,2][5,8][6,5][7,7][8,1]
[1,3][2,6][3,8][4,1][5,4][6,7][7,5][8,2]
[1,3][2,6][3,8][4,1][5,5][6,7][7,2][8,4]
[1,3][2,6][3,8][4,2][5,4][6,1][7,7][8,5]
[1,3][2,7][3,2][4,8][5,5][6,1][7,4][8,6]
[1,3][2,7][3,2][4,8][5,6][6,4][7,1][8,5]
[1,3][2,8][3,4][4,7][5,1][6,6][7,2][8,5]
[1,4][2,1][3,5][4,8][5,2][6,7][7,3][8,6]
[1,4][2,1][3,5][4,8][5,6][6,3][7,7][8,2]
[1,4][2,2][3,5][4,8][5,6][6,1][7,3][8,7]
[1,4][2,2][3,7][4,3][5,6][6,8][7,1][8,5]
[1,4][2,2][3,7][4,3][5,6][6,8][7,5][8,1]
[1,4][2,2][3,7][4,5][5,1][6,8][7,6][8,3]
[1,4][2,2][3,8][4,5][5,7][6,1][7,3][8,6]
[1,4][2,2][3,8][4,6][5,1][6,3][7,5][8,7]
[1,4][2,6][3,1][4,5][5,2][6,8][7,3][8,7]
[1,4][2,6][3,8][4,2][5,7][6,1][7,3][8,5]
[1,4][2,6][3,8][4,3][5,1][6,7][7,5][8,2]
[1,4][2,7][3,1][4,8][5,5][6,2][7,6][8,3]
[1,4][2,7][3,3][4,8][5,2][6,5][7,1][8,6]
[1,4][2,7][3,5][4,2][5,6][6,1][7,3][8,8]
[1,4][2,7][3,5][4,3][5,1][6,6][7,8][8,2]
[1,4][2,8][3,1][4,3][5,6][6,2][7,7][8,5]
[1,4][2,8][3,1][4,5][5,7][6,2][7,6][8,3]
[1,4][2,8][3,5][4,3][5,1][6,7][7,2][8,6]
[1,5][2,1][3,4][4,6][5,8][6,2][7,7][8,3]
[1,5][2,1][3,8][4,4][5,2][6,7][7,3][8,6]
[1,5][2,1][3,8][4,6][5,3][6,7][7,2][8,4]
[1,5][2,2][3,4][4,6][5,8][6,3][7,1][8,7]
[1,5][2,2][3,4][4,7][5,3][6,8][7,6][8,1]
[1,5][2,2][3,6][4,1][5,7][6,4][7,8][8,3]
[1,5][2,2][3,8][4,1][5,4][6,7][7,3][8,6]
[1,5][2,3][3,1][4,6][5,8][6,2][7,4][8,7]
[1,5][2,3][3,1][4,7][5,2][6,8][7,6][8,4]
[1,5][2,3][3,8][4,4][5,7][6,1][7,6][8,2]
[1,5][2,7][3,1][4,3][5,8][6,6][7,4][8,2]
[1,5][2,7][3,1][4,4][5,2][6,8][7,6][8,3]
[1,5][2,7][3,2][4,4][5,8][6,1][7,3][8,6]
[1,5][2,7][3,2][4,6][5,3][6,1][7,4][8,8]
[1,5][2,7][3,2][4,6][5,3][6,1][7,8][8,4]
[1,5][2,7][3,4][4,1][5,3][6,8][7,6][8,2]
[1,5][2,8][3,4][4,1][5,3][6,6][7,2][8,7]
[1,5][2,8][3,4][4,1][5,7][6,2][7,6][8,3]
[1,6][2,1][3,5][4,2][5,8][6,3][7,7][8,4]
[1,6][2,2][3,7][4,1][5,3][6,5][7,8][8,4]
[1,6][2,2][3,7][4,1][5,4][6,8][7,5][8,3]
[1,6][2,3][3,1][4,7][5,5][6,8][7,2][8,4]
[1,6][2,3][3,1][4,8][5,4][6,2][7,7][8,5]
[1,6][2,3][3,1][4,8][5,5][6,2][7,4][8,7]
[1,6][2,3][3,5][4,7][5,1][6,4][7,2][8,8]
[1,6][2,3][3,5][4,8][5,1][6,4][7,2][8,7]
[1,6][2,3][3,7][4,2][5,4][6,8][7,1][8,5]
[1,6][2,3][3,7][4,2][5,8][6,5][7,1][8,4]
[1,6][2,3][3,7][4,4][5,1][6,8][7,2][8,5]
[1,6][2,4][3,1][4,5][5,8][6,2][7,7][8,3]
[1,6][2,4][3,2][4,8][5,5][6,7][7,1][8,3]
[1,6][2,4][3,7][4,1][5,3][6,5][7,2][8,8]
[1,6][2,4][3,7][4,1][5,8][6,2][7,5][8,3]
[1,6][2,8][3,2][4,4][5,1][6,7][7,5][8,3]
[1,7][2,1][3,3][4,8][5,6][6,4][7,2][8,5]
[1,7][2,2][3,4][4,1][5,8][6,5][7,3][8,6]
[1,7][2,2][3,6][4,3][5,1][6,4][7,8][8,5]
[1,7][2,3][3,1][4,6][5,8][6,5][7,2][8,4]
[1,7][2,3][3,8][4,2][5,5][6,1][7,6][8,4]
[1,7][2,4][3,2][4,5][5,8][6,1][7,3][8,6]
[1,7][2,4][3,2][4,8][5,6][6,1][7,3][8,5]
[1,7][2,5][3,3][4,1][5,6][6,8][7,2][8,4]
[1,8][2,2][3,4][4,1][5,7][6,5][7,3][8,6]
[1,8][2,2][3,5][4,3][5,1][6,7][7,4][8,6]
[1,8][2,3][3,1][4,6][5,2][6,5][7,7][8,4]
[1,8][2,4][3,1][4,3][5,6][6,2][7,7][8,5]