【問題１】

  カエル（●）の配置

      ●●●○○○
      ○○○●●●
      ●●●○○○
      ○○○●●●
      ○●●○○●
      ●○○●●○

　考え方：上位の４行は自由に配置し、下位の２行で条件を合わせるようにした

【問題２】

（答え）

　　解の数　　　　３００４通り。ただし、鏡像解を別解としてカウントする場合は２４０３２通り。

　　美しい配置　　”美しい”の定義をどう考えるかによるが、
　　　　　　　　　”対対称解”という意味では、解は存在しない。
　　　　　　　　　”シンプルな解”と解釈すると、以下の配置あたりが候補になるかも

      　　　　　　　○○●●●○
      　　　　　　　●●●○○○
      　　　　　　　○○○●●●
      　　　　　　　●●●○○○
      　　　　　　　○○○●●●
      　　　　　　　●●○○○●

　　　　　　　      ○○○●●●
      　　　　　　　●●○○○●
      　　　　　　　●●○○○●
      　　　　　　　○○●●●○
      　　　　　　　○○●●●○
      　　　　　　　●●●○○○

（解法）

　　プログラムによる探索で全数を求めた。以下に、プログラムの基本的なアルゴリズムを説明する。

（１）準備
　　６ｘ６の領域を３ｘ３の４つの領域Ａ，Ｂ，Ｃ，Ｄに分けて考える。３ｘ３の領域の中に配置されたカエルの
　　数を＃（領域）で表すことにする。

　　　　　＋−−−＋−−−＋
　　　　　｜　　　｜　　　｜　　　　　＃（Ａ）＋　＃（Ｂ）　＝　９
　　　　　｜　Ａ　｜　Ｂ　｜　　　　　＃（Ｃ）＋　＃（Ｄ）　＝　９
　　　　　｜　　　｜　　　｜　　　　　＃（Ａ）＋　＃（Ｃ）　＝　９
　　　　　＋−−−＋−−−＋　　　　　＃（Ｂ）＋　＃（Ｄ）　＝　９
　　　　　｜　　　｜　　　｜
　　　　　｜　Ｃ　｜　Ｄ　｜　　　　　＃（Ａ）＝　αとすると
　　　　　｜　　　｜　　　｜　　　　　＃（Ｄ）＝　α、　＃（Ｂ）＝　＃（Ｃ）＝　９−α
　　　　　＋−−−＋−−−＋　　　　　となる

　　対角線上には、カエルが３匹存在しなければならないので、＃（Ａ）＋　＃（Ｄ）＞＝３　
　　これより、α＞＝２　　．．．．�@
　　また、鏡像解を除外するため、
　　　　　Ｙ軸対称を除外するために＃（Ａ）＜＝＃（Ｂ）とする。　これより、α＜＝４　　．．．．�A
　　　　　（Ｙ＝　Ｘ）軸対称性と（Ｙ＝−Ｘ）軸対称性は後述する

　　３ｘ３の領域に可能なカエルの配置を整理して、構造体配列　Ｍ［α］［　］を作成する。

　　　　　　Ｍ［α］［　］の構成要素を｛ｐ，ｕ，ｖ，ｘ１，ｘ２，ｘ３，ｙ１，ｙ２，ｙ３｝とする
　　　　　　　ｐ：９ビットのカエルの配置（下記の□を０／１で表す。１がカエルが存在する）
　　　　　　　α：３ｘ３の領域内のカエルの数
　　　　　　　　　　　  v　
　　　　　　　　　　 ／
　　　　　　□ □ □ → ｘ１
　　　　　　□ □ □ → ｘ２
　　　　　　□ □ □ → ｘ３　
　　　　　　↓ ↓ ↓ ＼
　　　　　　y1 y2 y3　 u　　
 
　　　　　　x1､x2､x3：Ｘ軸方向に存在するカエルの数
　　　　　　y1､y2､y3：Ｙ軸方向に存在するカエルの数
　　　　　　u　　　　：斜め方向（右下がり）に存在するカエルの数　
　　　　　　v　　　　：斜め方向（右上がり）に存在するカエルの数　

　　例えば、ｐ＝Ｂ’０１１０１１０００’（０ｘｄ８）の場合（ビット位置は、右下がＭＳＢ）
　　　　　　○○○　　　　　ｘ１＝０　　　ｙ１＝２　　ｕ＝１　　α＝４　　　
　　　　　　●●○　　　　　ｘ２＝２　　　ｙ２＝２　　ｖ＝２
　　　　　　●●○　　　　　ｘ３＝２　　　ｙ３＝０

　　　　　　Ｍ［４］［ｎ］＝｛０ｘｄ８，１，２，０，２，２，２，２，０｝となる

　　以上は、探索を効率よく行うための準備である。　　

（２）探索
　　探索は、４つの領域Ａ，Ｂ，Ｃ，Ｄの要素を配列Ｍから取り出して、６ｘ６の配置を生成し、条件に合致する
　　ものを選びだせばよい。
　　ただし、探索の効率の面から以下の条件で折り込む
　　　　−　＃（Ａ）は、２＜＝α＜＝４の範囲でよい（上記の�@,�Aより）
　　　　−　＃（Ｂ），＃（Ｃ）は、９−α、＃（Ｄ）はαの範囲
　　　　−　鏡像解を除外するため、（Ｙ＝　Ｘ）軸対称性と（Ｙ＝−Ｘ）軸対称性をチェックする
　　　　　　　Ａのｕ＞＝２　は除外する（Ａのｕ＜Ｄのｕとして鏡像解を除外する）
　　　　　　　Ｂのｖ＞＝２　は除外する（Ｂのｖ＜Ｃのｖとして鏡像解を除外する）

------(以下は探索プログラム）-------------------------------------------------------------------------

##### 20004.03.28
#
def  exe() :

     out = open("log.txt","w")

     M  = Init()

     Total = 0 
     for n in range(2,5) :
         Cnt = Join(n,M,out)
         Total += Cnt
         WriteLog(out,"\n  %d  :  %4d  %4d" % (n,Cnt,Total))

     out.close()

###
def  Init() :

     M = [[],[],[],[],[],[],[],[],[],[],[]]
    
     for k in range(0,512) :
         b = Bits(k)

         x1 = Bits(k & 0x07)
         x2 = Bits(k & 0x38)
         x3 = Bits(k & 0x1c0)

         y1 = Bits(k & 0x49)
         y2 = Bits(k & 0x92)
         y3 = Bits(k & 0x124)

         u  = Bits(k & 0x111)
         v  = Bits(k & 0x54)

         M[b] += [[k,u,v,x1,x2,x3,y1,y2,y3]]

     return M

###
def  Join(N,M,out) :

     Cnt = 0     
     for A in M[N] :
         [a,au,av,ax1,ax2,ax3,ay1,ay2,ay3] = A
         if  au >= 2   :  continue
 
         for D in M[N] :
             [d,du,dv,dx1,dx2,dx3,dy1,dy2,dy3] = D
             if au + du != 3 :  continue

             for B in M[9-N] :
                 [b,bu,bv,bx1,bx2,bx3,by1,by2,by3] = B
                 if bv >= 2      :  continue
 
                 if ax1+bx1 != 3 :  continue
                 if ax2+bx2 != 3 :  continue
                 if ax3+bx3 != 3 :  continue

                 if dy1+by1 != 3 :  continue
                 if dy2+by2 != 3 :  continue
                 if dy3+by3 != 3 :  continue

                 for C in M[9-N] :
                     [c,cu,cv,cx1,cx2,cx3,cy1,cy2,cy3] = C
                     if bv + cv != 3 :  continue

                     if ay1+cy1 != 3 :  continue
                     if ay2+cy2 != 3 :  continue
                     if ay3+cy3 != 3 :  continue

                     if dx1+cx1 != 3 :  continue
                     if dx2+cx2 != 3 :  continue
                     if dx3+cx3 != 3 :  continue

                     Cnt += 1
                     if (N == 2) :
                        printMap(out,Cnt,a,b,c,d)
     return Cnt

###
def  Bits(K) :
     w = K
     c = 0
     while w != 0 :
        c += 1
        w = w & (w-1)
     return c
           
###
def  printMap(out,Cnt,a,b,c,d) :
     Line ="\n%4d  [%3x,%3x,%3x,%3x]" % (Cnt,a,b,c,d)
     WriteLog(out,Line)

     printMap2(out,((a>>0) & 0x007) + ((b<<3) & 0x38))
     printMap2(out,((a>>3) & 0x007) + ((b>>0) & 0x38))
     printMap2(out,((a>>6) & 0x007) + ((b>>3) & 0x38))
     printMap2(out,((c>>0) & 0x007) + ((d<<3) & 0x38))
     printMap2(out,((c>>3) & 0x007) + ((d>>0) & 0x38))
     printMap2(out,((c>>6) & 0x007) + ((d>>3) & 0x38))

def  printMap2(out,Map) :
     m = Map
     C = ["○","●"]
     Line = "      "
     for n in range(0,6) :
         Line += C[(m & 0x01)]
         m = m >> 1
     WriteLog(out,Line)

###
def  WriteLog(out,Line) :
     print Line
     out.write(Line+"\n")
     out.flush()

----------------------------------------------------------------------------------------------