|
|
問題
平面上に、n×n個の点が格子状に配置されている。
その中から次の条件を満たすような2n個の点を選ぶことができるだろうか。
条件：2n個の点のうち、どの３点を選んでも同一直線上にはない
答え
n= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …
0, 1, 2,11,32,50,132,380,368,1135,1120, …
n= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …
0, 1, 1, 4, 5, 11, 22, 57, 51,156,158, …
異なる解の個数を求めるように修正してみました。
LET t0=TIME
PUBLIC NUMERIC N !N×N個の格子 ※N≧1
LET N=6
PUBLIC NUMERIC s(8) !解の数
MAT s=ZER
PUBLIC NUMERIC C(50),C2(100),C3(100) !列、斜め方向の数（チェック用） ※n個、2n個
MAT C=2*CON
MAT C2=2*CON
MAT C3=2*CON
PUBLIC NUMERIC XX(100),YY(100) !「点」の座標 ※2n個
PUBLIC NUMERIC TBL_GCD(50,50) !GCD(i,j)の値
FOR i=1 TO N-1
FOR j=i TO N-1
LET t=GCD(i,j)
LET TBL_GCD(i,j)=t !上三角
LET TBL_GCD(j,i)=t !下三角 ※対角線は上書きされる
NEXT j
NEXT i
DIM M(N,N) !「点」の配置
MAT M=ZER
CALL try(1,M)
IF s(1)=0 THEN PRINT "解なし"
MAT PRINT s;
PRINT "異なる解="; (s(1)+s(2)+s(3)+s(4)+s(5)+s(6)+s(7)+s(8))/8
PRINT "計算時間=";TIME-t0
END
EXTERNAL SUB try(p,M(,)) !バックトラック法（深さ優先）で検索する
LET T=2*p !「点」の数
LET YY(T-1)=p !p×nの矩形内の「点」を抽出する
LET YY(T)=p
FOR i=1 TO N-1 !１つの行p（水平線）で２個選ぶ ※COMB(N,2)
IF C(i)>0 AND C2(p+i)>0 AND C3(p-i+N)>0 THEN !１つの列（垂直線）、斜め（±45°）でも２個までとなる
LET FLG=0 !１行目と２行目なら、無条件に追加する
IF p>2 THEN CALL check(p,i,T-4,M, FLG) !３行目以上なら、斜めの直線を考慮する
IF FLG=0 THEN !※T-4： dy=-1では、GCD=1となるので、対象から除外してよい
LET M(p,i)=1 !１つ目の点をとる
LET C(i)=C(i)-1 !列
LET C2(p+i)=C2(p+i)-1 !45°斜め
LET C3(p-i+N)=C3(p-i+N)-1 !-45°斜め
LET XX(T-1)=i !※Tすなわちpによるスタックとなる
FOR j=i+1 TO N !（組合せ）
IF C(j)>0 AND C2(p+j)>0 AND C3(p-j+N)>0 THEN
LET FLG=0
IF p>2 THEN CALL check(p,j,T-4,M, FLG)
IF FLG=0 THEN
LET M(p,j)=1 !２つ目の点をとる
LET C(j)=C(j)-1
LET C2(p+j)=C2(p+j)-1
LET C3(p-j+N)=C3(p-j+N)-1
LET XX(T)=j
IF p=N THEN !全ての行が揃ったら
CALL MtxSymmetry(M) !解の対称性
PRINT "No."; s(1) !結果を表示する
MAT PRINT M;
!!!STOP !※１つのみ ←←←←←
ELSE
CALL try(p+1,M) !次の行へ
END IF
LET M(p,j)=0 !元に戻す
LET C(j)=C(j)+1
LET C2(p+j)=C2(p+j)+1
LET C3(p-j+N)=C3(p-j+N)+1
END IF
END IF
NEXT j
LET M(p,i)=0 !元に戻す
LET C(i)=C(i)+1
LET C2(p+i)=C2(p+i)+1
LET C3(p-i+N)=C3(p-i+N)+1
END IF
END IF
NEXT i
END SUB
EXTERNAL SUB check(Y0,X0,T,M(,), FLG) !斜めの直線に関して
LET FLG=1 !NG
FOR i=1 TO T !追加する点と既存の点を選ぶ
LET dx=XX(i)-X0 !傾き
LET ax=ABS(dx)
IF ax>1 THEN !垂直線（チェック済み）以外 ※またdx=±1では、GCD=1となるので、対象から除外してよい
LET dy=YY(i)-Y0 !※行が異なるため、Y0≠YY(i)からdy≠0（水平線以外）である。
LET ay=ABS(dy)
IF ax<>ay THEN !斜め（±45°）の直線（チェック済み）以外
!線上の格子点の個数
! ２つ端点が(x1,y1)、(x2,y2)なら、この端点を除いて、GCD(|x1-x2|,|y1-y2|)-1 個
LET G=TBL_GCD(ay,ax)
IF G>1 THEN !格子点の数が１以上なら
LET y=Y0 !始端
LET x=X0
FOR j=1 TO G-1
LET y=y+dy/G !線上の格子点
LET x=x+dx/G
IF M(y,x)=1 THEN EXIT SUB !もう１個が見つかったら、ＮＧ！
NEXT j
END IF
END IF
END IF
NEXT i
LET FLG=0 !すべての線分で確認したら、ＯＫ！
END SUB
!バーンサイドの定理（コーシー・フロベニウスの定理）
!集合A={対称なものを同一視しないで求めた解}
!置換群G={σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8}、|G|=8、 ※N次行列の要素の対称性より
! σ1 そのまま（恒等置換）
! σ2 反時計回りに90°回転
! σ3 反時計回りに180°回転
! σ4 反時計回りに270°回転
! σ5 左右裏返し ※裏返す軸は、「水平線（上下）」、「45°斜め線」、「-45°斜め線」でもよい
! σ6 左右裏返し + 反時計回りに90°回転
! σ7 左右裏返し + 反時計回りに180°回転
! σ8 左右裏返し + 反時計回りに270°回転
!S(X) Gの中の置換Xで変わらない、Aの中の不変元の個数
!とすると
! Aの同値類の個数m=Σ[σ∈G]{S(σ)} / |G|
! =( S(σ1)+S(σ2)+S(σ3)+S(σ4)+S(σ5)+S(σ6)+S(σ7)+S(σ8) ) / |G|
!となる。
EXTERNAL SUB MtxSymmetry(M(,)) !解の対称性
DIM B(N,N),B2(N,N)
LET s(1)=s(1)+1 !そのまま
CALL MtxR90(M,B) !90°回転対称な解の数
CALL MtxIsEqual(M,B, FLG)
LET s(2)=s(2)+FLG !FLGは、０または１とする
CALL MtxR90(B,B2) !180°
CALL MtxIsEqual(M,B2, FLG)
LET s(3)=s(3)+FLG
CALL MtxR90(B2,B) !270°
CALL MtxIsEqual(M,B, FLG)
LET s(4)=s(4)+FLG
CALL MtxLR(M,B2) !左右裏返し
CALL MtxIsEqual(M,B2, FLG)
LET s(5)=s(5)+FLG
CALL MtxR90(B2,B) !左右 + 90°
CALL MtxIsEqual(M,B, FLG)
LET s(6)=s(6)+FLG
CALL MtxR90(B,B2) !左右 + 180°
CALL MtxIsEqual(M,B2, FLG)
LET s(7)=s(7)+FLG
CALL MtxR90(B2,B) !左右 + 270°
CALL MtxIsEqual(M,B, FLG)
LET s(8)=s(8)+FLG
SUB MtxIsEqual(A(,),B(,), FLG) !A=Bか確認する ※FLG=1なら、一致
LET FLG=0
FOR i=1 TO N
FOR j=1 TO N
IF A(i,j)<>B(i,j) THEN EXIT SUB
NEXT j
NEXT i
LET FLG=1 !すべてが一致する
END SUB
SUB MtxLR(M(,), B(,)) !左右裏返し（列の順序を逆にする） ※変数名M≠変数名B
FOR i=1 TO N
FOR j=1 TO N
LET B(i,N-j+1)=M(i,j)
NEXT j
NEXT i
END SUB
SUB MtxR90(M(,), B(,)) !反時計回りに90°回転 ※変数名M≠変数名B
FOR i=1 TO N
FOR j=1 TO N
LET B(N-j+1,i)=M(i,j)
NEXT j
NEXT i
END SUB
END SUB
EXTERNAL FUNCTION GCD(a,b) !最大公約数
DO WHILE b<>0
LET t=b
LET b=MOD(a,b)
LET a=t
LOOP
LET GCD=a
END FUNCTION
補足
N=6
●●・・・・ １
・・・●・●
・●・・●・
●・●・・・
・・・・●●
・・●●・・
●●・・・・ ２
・・・●・●
・・●・●・
●・●・・・
・●・・・●
・・・●●・
●・●・・・ ３
・・●・●・
●●・・・・
・・・・●●
・●・●・・
・・・●・●
●・●・・・ ４
・・・●●・
・●・・・●
●●・・・・
・・・・●●
・・●●・・
●・●・・・ ５
・・・・●●
・●・・●・
●●・・・・
・・・●・●
・・●●・・
・●●・・・ ６
●・・・●・
●・●・・・
・・・●・●
・●・・・●
・・・●●・
・●●・・・ ７
・・●・●・
●・・・・●
●・・・・●
・●・●・・
・・・●●・
・●●・・・ ８
・・●・・●
・・・・●●
●●・・・・
●・・●・・
・・・●●・
・●●・・・ ９
・・・・●●
●・●・・・
・・・●・●
●●・・・・
・・・●●・
・●・●・・ 10
・・●・・●
●・・・●・
・●・・・●
●・・●・・
・・●・●・
・●・●・・ 11
・・・●・●
●●・・・・
・・・・●●
●・●・・・
・・●・●・
|
|