「 今週のお題：n-Queenで反転」問題解答 ( CodeIQ )

CodeIQ

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 入力 n ( nは7以下 ) に対し、n×nのオセロを考える
  • 全てのマスが白の状態から、何回の操作で全てを黒にできるか、最小の操作回数を出力する。ただし、できない場合は 0 を出力する。
  • 行う操作は「n-Queenの配置を満たす1組のマスでオセロを全て裏返す」こと

解説

まずは愚直にn-Queenの配置を求めます。マスの座標を$(0,y_0),(1,y_1),\cdots,(n-1,y_{n -1})$とした時、各 y は 0～n-1の順列になっています。これに、斜めでアタリにならない条件を加味して求めます。

それで、問題の条件を満たすには、対角線上にある、すなわち各$i$に対して $(i,i)$ を含む配置が n個分必要になりますので、それが1つでも欠けていれば 0、あれば n個での組み合わせを試します。

なお、全て裏返ったかどうかは、各マスをbitで表現して、n個の配置全て xor を取って、全bitが1になること、で判定できます。

実際に提出したのは、次のRubyのコードです。

n=gets.to_i
a=[]
# n-Queenの配置をbit列 ( n*n bit整数 ) 化して保存
(0..n-1).to_a.permutation{|r|
  s1=s2=0
  enc=r.each_with_index.reduce(0){|s,(e,i)|
    t=1<<e
    break if s1&t>0||s2&t>0
    s1=(s1|t)<<1
    s2=(s2|t)>>1
    s|(t<<(i*n))
  } and a<<enc
}
# 全てが裏返った状態の表現
full=(1<<(n*n))-1

# 対角線 ( 上からと右からの距離が等しいマス ) 上のマスを含む配置を分類
x=(0..n-1).map{|i|a.find_all{|e|e[i*(n+1)]>0}}
f=->i,s{
  if i==n-1
    x[i].each{|e|
      return [e] if e|s==full
    }
  else
    x[i].each{|e|
      t=f[i+1,s|e] and return t+[e]
    }
  end
  nil
}
# 対角線上の全マスが埋まらなければ 0、そうでない場合、n組でいけるのでは…?
puts x.any?{|r|r.size<1}?0:f[0,0]?n:"unknown"

終わりに

問題のケースは $n\le 7$ なのでそれで行けるましたが、$n\ge 8$ だともうちょっと別の手を考える必要がありそうです。…良い手、あるんでしょうか??