TSfree 発言

廣島です．
> 
> 勿論，初期配置によっては解けなかったり(Contradiction)，
> 解が一意に定まらなかったりします．
> 

前回のアルゴリズムはいまいち信用ならないので，
解をすべて数えあげるように，Puzzle クラスを変更しました．

使い方は同じで，

puzzle = Puzzle.new
puzzle.solve

または，

OTHERSETUP = [
  [0, 0, 1, 0, 0, 0],
  [0, 3, 0, 0, 0, 0],
  [4, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 5],
  [0, 0, 0, 0, 6, 0],
  [0, 0, 0, 5, 0, 2],
]

puzzle = Puzzle.new
puzzle.solve OTHERSETUP

です．

ruby -s puzzle.rb -v

と起動すると，背理法で候補を消去する過程を表示します．
-----------------------------
	廣島 勉
	(tsutomu@...)

class Puzzle
  
  class Contradiction < Exception
  end
    
  class Cell < Array

    def initialize
      replace((1..6).to_a)
      @raw = []
      @column = []
    end

    def mate(c)
      @partner = c
    end

    def mate?(c)
      ! @partner.nil? && @partner.equal?(c)
    end

    def same_raw(c)
      @raw.push(c)
    end

    def same_column(c)
      @column.push(c)
    end

    def parity
      return 1 if find { |n| n & 1 == 0 }.nil?
      return 0 if find { |n| n & 1 == 1 }.nil?
    end

    def unique(n)
      return false unless include?(n)
      if @raw.find { |c| c.include?(n) }.nil?
	fix(n)
	return true
      elsif @column.find { |c| c.include?(n) }.nil?
	fix(n)
	return true
      end
      return false
    end

    def fix_unique(n)
      @raw.each { |c| break if c.unique(n) }
      @column.each { |c| break if c.unique(n) }
    end

    def cross_off_fixed
      n = first
      @raw.each { |c| c.cross_off(n) }
      @column.each { |c| c.cross_off(n) }
    end

    def cross_off_parity
      return if (p = @partner.parity).nil?
      raise Contradiction.new if p == q = parity
      (2 - p).step(6 - p, 2) { |n| cross_off(n) } if q.nil?
    end

    def fix(n)
      return if n == 0 || self == [n]      
      raise Contradiction.new unless include?(n)
      cs = self - [n]
      self.replace([n])
      cross_off_fixed
      @partner.cross_off_parity unless @partner.nil?
      cs.each { |n| fix_unique(n) }
    end

    def cross_off(n)
      raise Contradiction.new if self == [n]
      return unless include?(n)
      delete(n)
      if size == 1
	cross_off_fixed
      else
	fix_unique(n)
      end
      @partner.cross_off_parity unless @partner.nil?
    end

    def to_s
      s = map { |n| n.to_s }.join
      sprintf "%-6s", " " * ((6 - s.length) / 2) + s 
    end

    def clone
      Cell.new.replace(self)
    end

  end # class Cell

  def mate(a, b)
    a.mate(b)
    b.mate(a)
  end

  def same_column(a, b)
    a.same_column(b)
    b.same_column(a)
  end

  def same_raw(a, b)
    a.same_raw(b)
    b.same_raw(a)
  end

  CELL = Array.new(6, Array.new(6))
  def initialize(cell = CELL.map { |r| r.map { |c| Cell.new } })
    @cell = cell
    0.upto(5) do |x|
      0.upto(5) do |y|
	(x + 1).upto(5) { |i| same_column(@cell[i][y], @cell[x][y]) }
	(y + 1).upto(5) { |j| same_raw(@cell[x][j], @cell[x][y]) }
      end
    end    
    0.step(4, 2) do |i|
      1.step(3, 2) do |j|
	mate(@cell[i][j], @cell[i][j + 1])
      end
    end
    1.step(5, 2) do |i|
      0.step(4, 2) do |j|
	mate(@cell[i][j], @cell[i][j + 1])
      end
    end
  end

  def clone
    Puzzle.new(@cell.map { |r| r.map { |c| c.clone } })
  end
  
  HR = '+' + '-' * 47 + "+\n"
  def display
    print HR
    0.upto(5) do |i|
      print '|'
      0.upto(5) do |j|
	print ' ' + @cell[i][j].to_s, j != 5 && (i + j) & 1 == 1 ?  ' ' : '|'
      end
      print "\n", HR
    end
  end

  def next_unfixed_cell(x, y)
    y.upto(5) do |j|
      return x, j if @cell[x][j].size > 1
    end
    (x + 1).upto(5) do |i|
      0.upto(5) do |j|
	return i, j  if @cell[i][j].size > 1
      end
    end
    return
  end

  def fix(i, j, n)
    @cell[i][j].fix(n)
  end
  
  def cross_off(i, j, n)
    @cell[i][j].cross_off(n)
  end

  @@verbose = defined? $v

  def self.verbose=(v)
    @@verbose = v
  end

  def verbose(d, m)
    print ' ' * d, "#{d}:#{m}\n" if @@verbose
  end

  def assume(i, j, k = 0, d = 0)
    c = @cell[i][j].clone
    verbose(d, "Posibility: Cell(#{i}, #{j}) = #{c.join(',')}")
    c.each do |n|
      assumption = clone
      begin
	assumption.fix(i, j, n)
	verbose(d, "Assume: Cell(#{i}, #{j}) = #{n}")
	x, y = assumption.next_unfixed_cell(i, j + 1)
	if x.nil?
	  print "\nSolution #{k += 1}\n"
	  assumption.display
	else
	  k = assumption.assume(x, y, k, d + 1)
	end
      rescue Contradiction
	verbose(d, "Contradiction: Cell(#{i}, #{j}) != #{n}")
	begin
	  cross_off(i, j, n)
	rescue Contradiction => e
	  verbose(d, "Exclude: Cell(#{i}, #{j}) != #{c.join(',')}")
	  raise e
	end
      end
    end
    return k
  end

  SETUP = [
    [6, 0, 5, 0, 0, 0], 
    [0, 6, 0, 0, 0, 0],
    [4, 0, 0, 0, 0, 0],
    [0, 0, 0, 4, 0, 1],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 5, 0, 0],
  ]

  def setup(c = SETUP)
    print "Setup...\n", HR
    0.upto(5) do |i|
      print '|'
      0.upto(5) do |j|
	n = c[i][j]
	print '   ', n == 0 ? ' ' : n.to_s, '   '
	print j != 5 && (i + j) & 1 == 1 ? ' ' : '|'
      end
      print "\n" + HR
    end
    0.upto(5) do |i|
      0.upto(5) do |j|
	fix(i, j, c[i][j])
      end
    end
    if @@verbose
      print "Posibilities...\n"
      display
    end
  end

  def solve(c = SETUP)
    setup(c)
    i, j = next_unfixed_cell(0, 0)
    if i.nil?
      print "\nTotal: 1 Solution\n"
      return 1
    end
    k = assume(i, j)
    print "\nTotal: #{k} Solution", k > 1 ? "s\n" : "\n"
    return k
  rescue Contradiction
    print "\nNo Solution\n"
    return 0
  end

end # class Puzzle