解迷游戏可以用的2-sat谜题核心脚本

浮云半仙

2-sat问题是什么

2sat.zip (1.39 KB, 下载次数: 89)

2017-2-14 12:58 上传

点击文件名下载附件
脚本

 [pre lang="ruby"]=begin
描述：
n个布尔型变量b(0), b(1), ..., b(n-1) 。m个条件，用0表示假，用1表示真。
每个条件形如
b(x)为真/假 或者 b(y)为真/假
求一组符合所有条件的解(注：有可能无解)

这个脚本在游戏里面怎么用呢？
TwoSat.make2sat(n, m) 可以生成一个保证有解的2sat问题，n个bool变量m个条件
TwoSat#check_answer(ans) 给出一组解，检查是否可行。
=end
class TwoSat
  attr_reader :maxn
  attr_accessor :graph
  def initialize(n)
    @maxn = n
    @graph = Array.new(n*2) {[]}
    @dfn = Array.new(n*2, 0)
    @low = Array.new(n*2, 0)
    @scc = Array.new(n*2, 0)
    @scc_cnt = 0
    @dfn_time = 0
    @checked = false
    @Stk = []
  end
  def add_condition(x, y, xv, yv)
    return if x >= @maxn || y >= @maxn
    @graph[(2*x+xv)^1].push(2*y+yv)
    @graph[(2*y+yv)^1].push(2*x+xv)
  end
  def tarjan(u)
    @dfn_time += 1
    @low = @dfn = @dfn_time
    @stk.push(u)
    @graph.each do |to|
      if @dfn[to] == 0
        tarjan(to)
        @low = @low[to] if @low[to] < @low
      elsif @scc[to] == 0
        @low = @dfn[to] if @dfn[to] < @low
      end
    end
    if @low == @dfn
      @scc_cnt += 1
      while @stk.size != 0
        x = @stk.pop
        @scc[x] = @scc_cnt
        break if x == u
      end
    end
  end
  def pre_check
    if !@checked
      (0...@maxn*2).each do |i|
        tarjan(i) if @dfn == 0
      end
      @checked = true
    end
  end
  def answerable?  #检查是否有解
    pre_check
    (0...@maxn).each do |i|
      return false if @scc[i*2] == @scc[i*2+1]
    end
    return true
  end
        #检查答案. #一个长度为n的数组描述bool变量0~n-1的取值
  def check_answer(ans)
    pre_check
    @mark ||= Array.new(2*@maxn)
    @mark.fill(false)
    ans.each_with_index do |e, i|
      @mark[i*2+e] = true
    end
    (0...@maxn*2).each do |x|
      return false if @mark[x] && !bfs(x)
    end
    return true
  end
  def bfs(x)
    head = 0
    @q ||= Array.new(2*@maxn)
    @vis ||= Array.new(2*@maxn)
    @q[0] = x
    @vis.fill(false)
    @vis[x] = true
    tail = 1
    while(head < tail)
      u = @q[head]; head += 1
      return false if @mark != @mark[x]
      @graph.each do |to|
        if !@vis[to]
          @q[tail] = to
          tail += 1
          @vis[to] = true
        end
      end
    end
    return true
  end
  
  def self.make2sat(n, m) #生成一个n个bool变量，m个条件的2-sat问题
    while true
      s = self.new(n)
      cs = []
      m.times do
        x = rand(n)
        y = rand(n)
           #随机构造2-sat
        cs << [x, y, rand(2), rand(2)]
        s.add_condition(*cs.last)
      end
      return [s, cs] if s.answerable? #可解
    end
  end
   
end

=begin
s = TwoSat.new(2)                 #两个bool变量
s.add_condition(1, 0, 1, 1)       #添加约束   b(0)为真 || b(1)为真
puts s.answerable?                #是否有解 true
puts s.check_answer([1, 1])       #检查b(0) = 1, b(1) = 1是否可行 true
puts s.check_answer([1, 0])       #检查b(0) = 1, b(1) = 0是否可行 true
puts s.check_answer([0, 1])       #检查b(0) = 0, b(1) = 1是否可行 true
puts s.check_answer([0, 0])       #检查b(0) = 0, b(1) = 0是否可行 false
=end[/pre]