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

浮云半仙

2-sat问题是什么

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

2017-2-14 12:58 上传

点击文件名下载附件
脚本

 

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
    [url=home.php?mod=space&uid=33409]@Stk[/url] = []
  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[u] = @dfn[u] = @dfn_time
    @stk.push(u)
    @graph[u].each do |to|
      if @dfn[to] == 0
        tarjan(to)
        @low[u] = @low[to] if @low[to] < @low[u]
      elsif @scc[to] == 0 
        @low[u] = @dfn[to] if @dfn[to] < @low[u] 
      end
    end
    if @low[u] == @dfn[u]
      @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[i] == 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
    [url=home.php?mod=space&uid=25204]@mark[/url] ||= 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[u] != @mark[x]
      @graph[u].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

=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


    [url=home.php?mod=space&uid=33409]@Stk[/url] = []


  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[u] = @dfn[u] = @dfn_time


    @stk.push(u)


    @graph[u].each do |to|


      if @dfn[to] == 0


        tarjan(to)


        @low[u] = @low[to] if @low[to] < @low[u]


      elsif @scc[to] == 0 


        @low[u] = @dfn[to] if @dfn[to] < @low[u] 


      end


    end


    if @low[u] == @dfn[u]


      @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[i] == 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


    [url=home.php?mod=space&uid=25204]@mark[/url] ||= 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[u] != @mark[x]


      @graph[u].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