hossy online - といぼっくす

_ [プログラミング] 5×5のマス目に6個の○を 回転・裏返しありの場合

02/07のエントリで、回転がありの場合はとツッコミを頂きましたもので、もう少し続けてみます。前のエントリのコメントと内容が被っています。

5×5のマス目に6個の○を次の条件を満たすように書きます。

条件：各行・各列に少なくとも1個は○を書く。同じマスには2個以上の○を書くことはできない。

このとき、6個の○を書く方法は全部で何通りありますか。

この問題に条件を付け加えます。

回転あり - 問題

この4通りは回転してみると同じです。これらをあわせて1通りと数えたときに、答えはどうなるでしょう。

●□□●□　□□□□●　●□□□□　□□□□●
□●□□□　□□□●□　□●□□□　●□□●□
□□●□□　□□●□□　□□●□□　□□●□□
□□□●□　□●□□●　□□□●□　□●□□□
□□□□●　●□□□□　□●□□●　●□□□□

回転あり - プログラミングで その1

前回最初に作ったごり押しプログラムに変更を加えました。rubyです。

def g(a)
  b = []
  a.each do |i|
    x, y = yield(i%5, i/5, 4 - i%5, 4 - i/5)  # left, top, right, bottom
    b << y*5 + x
  end
  (a <=> b.sort) <= 0
end
 
def f(a, d, s)
  r = 0
  s.upto(24) do |i|
    a[d] = i
    x = {}
    y = {}
    0.upto(d) do |j|
      x[a[j] / 5] = true
      y[a[j] % 5] = true
    end
    if (x.size >= d) && (y.size >= d)
      if (d == 5)
        next unless g(a){|l, t, r, b| [t, r]}
        next unless g(a){|l, t, r, b| [r, b]}
        next unless g(a){|l, t, r, b| [b, l]}
        r += 1
      else
        r += f(a, d+1, i+1)
      end
    end
  end
  r
end
a = [0]*6
puts f(a, 0, 0)

正解かもしれない配置が見つかったときに、その配置を回転してみた3通りがについて以前に出てきていないかを調べます。left, top, right, bottomをそれぞれから数えて何番目かを示すとき、(left, top) を回転させると (top, right), (right, bottom), (bottom, left)。その回転したものとの大小関係を確かめて、問題なければ g(a) が true を返します。

回転あり - プログラミングで その2

この問題なら、もっと簡単に解く事が出来ます。

90度単位で回転を行うとき、だいたいの配置は4回動かしてはじめて元に戻ります。ですので、前回の答えを4で割ったものがだいたいの答えになります。

だいたいというのは、一部だけ2回動かして元に戻るものがあるためです。点対称。

□□●□□
□●□□□
●□□□●
□□□●□
□□●□□
 
□□●□□
□□□●□
●□□□●
□●□□□
□□●□□

4で割ると割りすぎになります。2回動かすと戻るなら、2で割るのが正しい。そこで、4で割る前にこのようなケースを見つけると2個分と数えておきます。

点対称な配置は、左上から数えるかわりに右下から数えることで簡単に得られます。位置を24から引き算して、反転して、元と同じなら点対称。そうして書き直したものがこちら。

def f(a, d, s)
  r = 0
  s.upto(24) do |i|
    a[d] = i
    x = {}
    y = {}
    0.upto(d) do |j|
      x[a[j] / 5] = true
      y[a[j] % 5] = true
    end
    if (x.size >= d) && (y.size >= d)
      if (d == 5)
        r += 1
        r += 1 if a.reverse.map{|x| 24-x} == a
      else
        r += f(a, d+1, i+1)
      end
    end
  end
  r
end
a = [0]*6
puts f(a, 0, 0) / 4

回転あり - 手で

点対称な場合の数は、全て書き出すことができる程度です。

□□●□□　□★□□□　★□□□□　□□●□□
□★□□□　□□●□□　□□●□□　★□□□□
●□□□●　●□□□●　□●□●□　□●□●□
□□□★□　□□●□□　□□●□□　□□□□★
□□●□□　□□□★□　□□□□★　□□●□□
 
□□●□□　□□□★□　□□□□★　□□●□□
□□□★□　□□●□□　□□●□□　□□□□★
●□□□●　●□□□●　□●□●□　□●□●□
□★□□□　□□●□□　□□●□□　★□□□□
□□●□□　□★□□□　★□□□□　□□●□□

●4つで中心軸を通る菱形を作り、残り★2個を配置すると、回転を意識しなかった時の8通り分という事が分かります。ですので正解は「(4200+8)/4 = 1052」（反転）となります。

回転・裏返しあり - 問題

更に裏から見た場合も同じと考えます。この8通りが同じと数えたときにはどうなるでしょう。

●□□●□　□□□□●　●□□□□　□□□□●
□●□□□　□□□●□　□●□□□　●□□●□
□□●□□　□□●□□　□□●□□　□□●□□
□□□●□　□●□□●　□□□●□　□●□□□
□□□□●　●□□□□　□●□□●　●□□□□
　
□□□□●　●□□□□　□●□□●　●□□□□
□□□●□　□●□□●　□□□●□　□●□□□
□□●□□　□□●□□　□□●□□　□□●□□
□●□□□　□□□●□　□●□□□　●□□●□
●□□●□　□□□□●　●□□□□　□□□□●

回転あり - プログラミングで

最初のコードに4行追加です。

        next unless g(a){|l, t, r, b| [t, r]}
        next unless g(a){|l, t, r, b| [r, b]}
        next unless g(a){|l, t, r, b| [b, l]}
        next unless g(a){|l, t, r, b| [t, l]}  # 追加
        next unless g(a){|l, t, r, b| [r, t]}  # 追加
        next unless g(a){|l, t, r, b| [b, r]}  # 追加
        next unless g(a){|l, t, r, b| [l, b]}  # 追加

これがしたかったために、最初のコードは長くなっていたのでした。

答えは「561」（反転）だそうです。

回転・裏返しあり - 手で？

手で解こうとしました。しかし、場合分けが大変で力尽きました（汗）。どなたか頑張ってください…