TSfree 発言

廣島です．

TSabc では，ちょっと，まずそうなので，TSfree に投稿します．

> 朝日新聞の土曜夕刊のパズルにコンピュータで答えが
> 出せそうな問題が出ていました。(2003年2月15日)

Puzzle クラスを ruby で書きました．(定義はサインの後に)

puzzle = Puzzle.new
puzzle.solve

で解いてくれます．

solve に数値の別の初期配置を与えることができます．

OTHERSETUP = [
  [0, 0, 1, 0, 0, 0],
  [0, 3, 0, 0, 0, 0],
  [4, 0, 2, 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

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

実行例: 上記初期配置の場合...
Setup...
+-----------------------------------------------+
|       |           1   |               |       |
+-----------------------------------------------+
|           3   |               |               |
+-----------------------------------------------+
|   4   |           2   |               |       |
+-----------------------------------------------+
|               |               |           5   |
+-----------------------------------------------+
|       |               |           6   |       |
+-----------------------------------------------+
|               |           5   |           2   |
+-----------------------------------------------+
Candidates...
+-----------------------------------------------+
|  2356 |  246      1   |  234     2345 |  346  |
+-----------------------------------------------+
|   26      3   |  456     124  |  1245    146  |
+-----------------------------------------------+
|   4   |   15      2   |   6      135  |   13  |
+-----------------------------------------------+
|  1236    1246 |  346     1234 |   24      5   |
+-----------------------------------------------+
|  1235 |  1245    345  |   13      6   |  134  |
+-----------------------------------------------+
|  136     146  |   46      5   |   13      2   |
+-----------------------------------------------+
Method of Elimination: Cell(0, 0) != 2
Method of Elimination: Cell(0, 0) != 6
Method of Elimination: Cell(0, 1) != 6
Method of Elimination: Cell(0, 3) != 3
Method of Elimination: Cell(0, 0) != 5
+-----------------------------------------------+
|   3   |   4       1   |   2       5   |   6   |
+-----------------------------------------------+
|   6       3   |   5       4   |   2       1   |
+-----------------------------------------------+
|   4   |   5       2   |   6       1   |   3   |
+-----------------------------------------------+
|   2       1   |   6       3   |   4       5   |
+-----------------------------------------------+
|   5   |   2       3   |   1       6   |   4   |
+-----------------------------------------------+
|   1       6   |   4       5   |   3       2   |
+-----------------------------------------------+
Solution is unique.

-----------------------------
	廣島 勉
	(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
    @cell.each do |r|
      print '|'
      0.upto(5) do |j|
	print ' ' + r[j].to_s, r[j].mate?(r[j + 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

  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 solve(c = SETUP)
    begin
      print "Setup...\n", HR
      0.upto(5) do |i|
	print '|'
	0.upto(5) do |j|
	  n = c[i][j]
	  print '   ', n == 0 ? ' ' : n, '   '
	  print @cell[i][j].mate?(@cell[i][j + 1]) ? ' ' : '|'
	  fix(i, j, n)
	end
	print "\n", HR
      end
      print "Candidates...\n"
      display
      i, j = next_unfixed_cell(0, 0)
      if i.nil?
	print "Solution is unique.\n"
	return
      end
      loop do
	n = nil
	begin
	  @cell[i][j].each do |n|
	    asumption = clone
	    asumption.fix(i, j, n)
	  end
	  i, j = next_unfixed_cell(i, j + 1)
	  if i.nil?
	    display
	    print "Solution is NOT unique.\n"
	    return
	  end
	rescue Contradiction
	  print "Method of Elimination: Cell(#{i}, #{j}) != #{n}\n"
	  cross_off(i, j, n)
	  i, j = next_unfixed_cell(0, 0)
	  if i.nil?
	    display
	    print "Solution is unique.\n"
	    return
	  end
	end
      end
    rescue Contradiction
      raise "Contradicted Setup"
    end
  end
end # class Puzzle