作者: Noritsugu Nakamura
日時: 2003/3/16(11:37)
中村 のりつぐ です。

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

--- ここから ---

 -------------------
 |6|  5|   | |
 -------------------
 |  6|   |   |
 -------------------
 |4|   |   | |
 -------------------
 |   |  4|  1|
 -------------------
 | |   |  1| |
 -------------------
 |   |  5|   |
 -------------------

 森の中を散歩中、レンガ造りのお屋敷に出会い
ました。主人はパズル好きらしく壁のレンガに数
字とともにこうあります。「縦の列で見ても横の
列で見ても1から6までの数字が一つずつ入るよ
うに空きを埋めてください。ただし長方形のレン
ガに入る数字は奇数と偶数のペアになるようにし
ます。解ければ当屋敷へご招待します」。さあ、
あなたは解けますか。

--- ここまで ---

悲しいことにまだちゃんとプログラムが書けていません。
brick の1箇所答えを教えて上げると解けるのですが、
どうやら組合せの機構を入れないとダメらしい…。

以下、とんでもなく途中なスクリプト。


#!/usr/bin/env ruby

D = [1, 2, 3, 4, 5, 6] 

brick = [
#  [6, 2, 5, D, D, D], # こうすれば解ける
  [6, D, 5, D, D, D], # このままでは解けない
  [D, 6, D, D, D, D],
  [4, D, D, D, D, D],
  [D, D, D, 4, D, 1],
  [D, D, D, D, 1, D],
  [D, D, D, 5, D, D],
]

# ペアの情報
PARTITION = [
  [nil, 2, 1, 4, 3, nil],
  [  1, 0, 3, 2, 5,   4],
]

# 結果の表示
def print_result(brick)
  puts "*" * 18
  brick.each do |i|
    p i
  end
  puts "*" * 18
end

# 全て確定したか?
def is_end?(brick)
  brick.each do |i|
    i.each do |j|
      # まだ決まっていないものあり
      if j.type == Array
        return false
      end
    end
  end
  return true
end

# 横方向を埋める
def get_candidate_row(brick, i, j)
  a = [1, 2, 3, 4, 5, 6]
  a -= brick[i]
  n = PARTITION[i % 2][j]
  if n != nil
    if brick[i][n].type == Fixnum
      # ペアがある場合、ペアが{偶数,奇数}の場合{偶数,奇数}を除く。
      a -= [2, 4, 6] if brick[i][n] % 2 == 0
      a -= [1, 3, 5] if brick[i][n] % 2 == 1
    elsif brick[i][n].type == Array
      # ペアの候補の中に{偶数,奇数}しかなかったら{偶数,奇数}は除く。
      a -= [2, 4, 6] if (brick[i][n] & [1, 3, 5]).empty?
      a -= [1, 3, 5] if (brick[i][n] & [2, 4, 6]).empty?
    end
  end
  #p ["+a", a]
  # なんだったけ?
  a.each do |x|
    f = true
    (0..5).each do |y|
      next if y == j
      #f = false if brick[i][y] == nil
      if brick[i][y].type == Array
        f = false if brick[i][y].include?(x)
      end
      #p ["++", i, y, brick[i][y], x]
    end
    return [x] if f
  end
  return a
end

# 縦方向を埋める
def get_candidate_column(brick, i, j)
  a = [1, 2, 3, 4, 5, 6]
  (0..5).each {|x| a.delete(brick[x][j])}
  return a
end

def get_candidate(brick, i, j)
  a = get_candidate_row(brick, i, j)
  #p ["*a", a]
  b = get_candidate_column(brick, i, j)
  #p ["*b", b]
  return a & b
end

def try_fill_box(brick)
  (0..1).each do |k| # 2回回してみれば、分かる?
    (0..5).each do |i|
      (0..5).each do |j|
        next if brick[i][j].type == Fixnum # 既に決定済みなのでスキップ
        a = get_candidate(brick, i, j); brick[i][j] = a
        #p [i, j, a]
        if a.size == 1
          brick[i][j] = a[0]
          #p ["=", i, j, a[0]]
          #print_result(brick)
          return true
        end
      end
    end
  end
  return false
end

# main

until is_end?(brick)
  try_fill_box(brick)
end

print_result(brick)

       中村 典嗣  E-mail:     nnakamur@...