[ruby-list:6601] 8-queen

高橋です。今度ちゃんと1.1b7にします……と書こうとしたら、b8になって
いるし……。

パズル関係がほしい、ということだったので(どうしてなのでしょうか？)、
8-queenを作ってみました。生まれてはじめてスレッドを使ってみました(^^)
が、あんまり意味はないです(^_^;  順列を生成するイテレータを使っている
のがrubyっぽいかも。

スレッドの使い方にはいまひとつ自信がないです。最後に終了してほしく
てこうしてみたのですが、他にいいやり方はあるのでしょうか？


#!/usr/local/bin/ruby
#
# 8 queen
#
# 使い方：実行するだけ :-)
#
# 出力の見方：8個の数字が並びます。それぞれ、一列目のクイーンの場所、
#             二列目のクイーンの場所、……と思って下さい。
#
# 参考：「perl書法」（アスキー、だったはず）
#       upとdownの連想配列のアイデアはここからいただきました。
#

require "thread"

queen_num = 8  # queenの数
q = Queue.new


### class method

class Array
  def each_perm
    a = self
    elem = a.shift
    if a.size > 0
      a.each_perm{|a_sub_perm|
	for j in 0..a_sub_perm.size
	  yield a_sub_perm.insert_elem(j,elem)
	end
      }
    else
      yield a+elem
    end
  end

  def valid?
    up = {}
    down = {}
    self.each_index{|i|
      if up[i+self[i]]  or down[i-self[i]]
	return FALSE
      else
	up[i+self[i]] = TRUE
	down[i-self[i]] = TRUE
      end
    }
    return TRUE
  end
        
  def insert_elem(i,elem)
    self[0,i] + [elem] + self[i,self.size]
  end
end


### function

def make_queens(n)
  queens = []
  for i in 1..n
    queens << i
  end
  queens
end


### main

queens = make_queens(queen_num)

Thread.start {
  queens.each_perm{|i|
    q.push i
  }
  q.push "END"
}
  
while list=q.pop
  if list == "END"
    Thread.exit
  elsif list.valid?
    print list,"\n"
  end
end