2.7 Nクイーン問題の解法

#!/usr/bin/env ruby
#encoding: utf-8
require "zdd"

n = 5

# 以下の二重ループにて、25マス(アイテム)の全組み合わせのアイテム集合が列挙され、変数allに格納される。
# アイテム名には座標を示した文字列"i,j"を用いている。
all=ZDD.constant(1)
(0...n).each{|i|
	(0...n).each{|j|
		all *= (1+ZDD::itemset("#{i},#{j}"))
	}
}

# 以下で、お互いに取られる2マスの組み合せを全列挙し、変数ngに格納する。
ng=ZDD.constant(0)
(0...n).each{|i| # 行ループ
  (0...n).each{|j| # 列ループ
     # マス目i,jと同じ行番号(i)を持つアイテムペア
    (j+1...n).each{|k|
      ng+=ZDD::itemset("#{i},#{j} #{i},#{k}") # 横
    }
     # マス目i,jと同じ列番号(j)を持つアイテムペア
    (i+1...n).each{|k|
      ng+=ZDD::itemset("#{i},#{j} #{k},#{j}") # 横
    }
    # マス目i,jと、そこから右斜め下方向のアイテムペア
    (1...[n-i,n-j].min).each{|k|
      ng+=ZDD::itemset("#{i},#{j} #{i+k},#{j+k}") #
    }
    # マス目i,jと、そこから左斜め下方向のアイテムペア
    (1...[n-i,j+1].min).each{|k|
      ng+=ZDD::itemset("#{i},#{j} #{i+k},#{j-k}") #
    }
  }
}
st=Time.new # 時間計測用
selNG=all.restrict(ng)     # 1) 全アイテム集合allからお互いに取られるアイテムペアを含むアイテム集合を選択する。
selOK=selNG.iif(0,all)     # 2) 全アイテム集合allから、1)で求めたアイテム集合を除外する。
selLT=selOK.permitsym(n-1) # 3) 2)の結果から、サイズがn-1以下のアイテム集合を選択する。
ans  =selLT.iif(0,selOK)   # 4) 2)の結果から3)で求めたアイテム集合を除外する。

# 計算過程で作成されたZDDのアイテム集合(totalweight関数)の数、およびZDDの接点数(size関数)を表示する。
# totalweight関数はZDDの各項の重みを合計するメソッドである。
# ここでは、全ての項の重みは1なので、結果として式に含まれるアイテム集合の数が分かる。
puts "all   : #{all.totalweight}\t #{all.size}"
puts "selNG : #{selNG.totalweight}\t #{selNG.size}"
puts "selOK : #{selOK.totalweight}\t #{selOK.size}"
puts "selLT : #{selLT.totalweight}\t #{selLT.size}"
puts "ans   : #{ans.totalweight}\t #{ans.size}"
puts "time: #{Time.new-st}"
ans.show # 解の表示