【問題１】 　６×６の場合、最少でいくつの○を置き換えれば、条件を満たすことができるでしょうか。 　またその場合の配置を示してください。 （答え）７個 　　○×○○○○ 　　○○○○×○ 　　○○×○○○ 　　×○○○○× 　　○○○×○○ 　　○×○○○○ 【問題２】 　７×７の場合、最少でいくつの○を置き換えれば、条件を満たすことができるでしょうか。 　またその場合の配置を示してください。 　問題１より簡単かもしれません。 （答え）９個 　　○○○○×○○ 　　○○×○○○○ 　　×○○○○×○ 　　○○○×○○○ 　　○×○○○○× 　　○○○○×○○ 　　○○×○○○○ 【問題３】 　５×５の場合、最少個数５個の解は何通りあるでしょうか。 （答え）プログラム（最後に添付）による探索の結果、反転対称解（鏡像解）を同一として 　　　　数えた場合は、以下の１１個。別物とした場合は、４８個 1 : ( 0, 0 ) ( 1, 1 ) ( 2, 2 ) ( 3, 3 ) ( 4, 4 ) 2 : ( 0, 0 ) ( 1, 1 ) ( 2, 2 ) ( 3, 4 ) ( 4, 3 ) 3 : ( 0, 0 ) ( 1, 2 ) ( 2, 3 ) ( 3, 1 ) ( 4, 4 ) 4 : ( 0, 0 ) ( 1, 2 ) ( 2, 4 ) ( 3, 1 ) ( 4, 3 ) 5 : ( 0, 0 ) ( 1, 3 ) ( 2, 2 ) ( 3, 1 ) ( 4, 4 ) 6 : ( 0, 0 ) ( 1, 3 ) ( 2, 2 ) ( 3, 4 ) ( 4, 1 ) 7 : ( 0, 0 ) ( 1, 3 ) ( 2, 4 ) ( 3, 1 ) ( 4, 2 ) 8 : ( 0, 0 ) ( 1, 3 ) ( 2, 4 ) ( 3, 2 ) ( 4, 1 ) 9 : ( 0, 0 ) ( 1, 4 ) ( 2, 2 ) ( 3, 3 ) ( 4, 1 ) 10 : ( 0, 1 ) ( 1, 0 ) ( 2, 2 ) ( 3, 4 ) ( 4, 3 ) 11 : ( 0, 1 ) ( 1, 4 ) ( 2, 2 ) ( 3, 0 ) ( 4, 3 ) 【おまけ】 　ｎ×ｎの場合は最少でいくつの○を置き換えれば、条件を満たすことができるでしょうか。 　ｎの式で表してください。 （答え）最小の×の数をＲ（ｎ）、ｎ＝５＊ｋ＋ｍ（ｋは自然数、ｍは０〜４の整数）とすると、 　　　　Ｒ（ｎ）＝５＊ｋ＊＊２　＋　２＊ｋ＊ｍ　＋　δ（ｍ） 　　　　　ただし、δ（Ｍ）＝　０　　　ｍ＝０，１，２の場合 　　　　　　　　　　　　　＝　１　　　ｍ＝３の場合 　　　　　　　　　　　　　＝　３　　　ｍ＝４の場合 　 （説明） 　境界を意識しないで済むような大きなパネル上に○が敷き詰められているものとする。 　このパネル上に×のマークを桂馬跳びの要領で以下の図のようにつけていく。　 　 　　●○○○○|●○○○○|●○○○○ 　　○○○●○|○○○●○|○○○●○　　注：見易さために、×の代りに●で表示 　　○●○○○|○●○○○|○●○○○　　　　５個毎に仕切り（−，｜）を入れて 　　○○○○●|○○○○●|○○○○●　　　　あるが、この仕切りは無視してよい 　　○○●○○|○○●○○|○○●○○　　　（斜めの関係を見るときはない方がよい）　 　　------------------------------ 　　●○○○○|●○○○○|●○○○○ 　　○○○●○|○○○●○|○○○●○ 　　○●○○○|○●○○○|○●○○○ 　　○○○○●|○○○○●|○○○○● 　　○○●○○|○○●○○|○○●○○ 　　------------------------------ 　　●○○○○|●○○○○|●○○○○　 　　○○○●○|○○○●○|○○○●○ 　　○●○○○|○●○○○|○●○○○ 　　○○○○●|○○○○●|○○○○● 　　○○●○○|○○●○○|○○●○○ 　この配置には以下のような特徴がある。 　　（１）任意の×とその隣の×との距離は、縦・横・斜めの全てが丁度４つの○を間に置いている 　　（２）任意の位置から５ｘ５のパネルを切り出すと、丁度５個の×が含まれる 　　（３）任意の位置から５ｘｍ又はｍｘ５のパネルを切り出すと、丁度ｍ個の×が含まれる 　（１）から、×の配置の仕方として全く無駄のないものとなっている。 　従って、このパネルからｎｘｎの小パネルを切り出す場合に、×の数が最小となるような位置を選 　　　　　＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾ 　定すれば、ｎｘｎの求める答えの１つとなる。 　＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾ 　 　具体的な×の数を求めるため、ｎ＝５＊Ｋ＋ｍ　（ｍ＝０〜４）として、ｎｘｎのパネルを 　以下の小パネルに分解して考える。 　　　ａ）５ｋｘ５ｋのパネル 　　　ｂ）５ｋｘｍのパネル 　　　ｃ）ｍｘ５ｋのパネル 　　　ｄ）ｍｘｍのパネル 　ａ）は、５ｘ５のパネルがｋ＊＊２個と考えることができるので、上記の（２）により×の 　数は、その位置によらず、５＊ｋ＊＊２個となる。また、ｂ），ｃ）も５ｘｍ、ｍｘ５のパ 　ネルがｋ個と考えられるので、上記の（３），（４）により×の数は、その位置によらず、 　それぞれがｋ＊ｍ個となる。 　ｄ）のｍｘｍのパネルの場合は、どの位置に配置するかに依存して×の数が変わる。×の最 　小となる数をδ（ｍ）とすると、以下のようになる。（最初の図を良く見るとわかる） 　　　　δ（ｍ）＝　０　　ｍ＝０，１，２の場合 　　　　　　　　　　１　　ｍ＝３の場合 　　　　　　　　　　３　　ｍ＝４の場合 　以上をまとめると、以下の式となる。　　　 　　　　Ｒ（ｎ）＝５＊ｋ＊＊２　＋　２＊ｋ＊ｍ　＋　δ（ｍ） 　なお、問題１，２の場合は、それぞれＲ（６）＝７，Ｒ（７）＝９となる。　 ------------　問題３の探索プログラム　---------------------------------------------- def exe() : out = open("log.txt","w") M = 5 C = 0 D = 0 for hash in range(0,120) : Pos = toPos(hash,M) if Check(Pos) == 0 : continue D += 1 if DupCheck(Pos,out) == 0 : continue C += 1 Line = " %3d : " % (C) for k in range(0,5) : Line += " ( %d, %d )" % (k,Pos[k]) WriteLog(out,Line) Check(Pos) WriteLog(out," Dup %d " % (D)) out.close() ### def Check(Pos) : U = 0 V = 0 for i in range(0,len(Pos)) : j = Pos[i] if (i == j) : U = 1 if (i+j == 4) : V = 1 if (U == 0) | (V == 0) : return 0 return 1 ## def toPos(Hash,M) : h = Hash Pos = [] for k in range(0,M) : Pos += [0] for k in range(0,M) : n = 6 - M + k p = h % n h = h / n Pos[M-k-1] = p for i in range(M-2,-1,-1) : for j in range(i+1,M) : if Pos[i] <= Pos[j] : Pos[j] += 1 return Pos ## def DupCheck(Pos,out) : for t in range(0,8) : w = Pos if (t & 0x01) != 0 : u = [[],[],[],[],[]] for k in range(0,len(Pos)) : u[k] = 4 - w[k] w = u if (t & 0x02) != 0 : u = [[],[],[],[],[]] for k in range(0,len(Pos)) : u[k] = w[4-k] w = u if (t & 0x04) != 0 : u = [[],[],[],[],[]] for k in range(0,len(Pos)) : u[w[k]] = k w = u if Pos > w : return 0 return 1 ### def WriteLog(out,Line) : print Line out.write(Line+"\n") out.flush() -------(終わり）------------------------------------------------------------------------