|
|
> No.1776[元記事へ]
GAIさんへのお返事です。
> ４×４の平方魔方陣して
>
> 68^2 29^2 41^2 37^2
>
> 17^2 31^2 79^2 32^2
>
> 59^2 28^2 23^2 61^2
>
> 11^2 77^2 8^2 49^2
>
> （1770年にオイラーがラグランジュへ教えたの記事を見る。）
30分程度で解を見つけることができます。この魔方陣専用のコーディングになっています。
斜め 高々C(212,2)×4!/2×4!/2通り
1行目 高々210×2!通り
これを埋めることによって、
2列目 高々209通り
3列目 高々208通り
4行目 高々207通り
が確定する。
同様に、
1列目 高々206×2!通り
2行目 高々205通り
3行目 高々204通り
4列目 高々203通り
で確認しています。
!平方数による４×４魔方陣
!実行結果
!
!No. 1
! 105 181 77 193 82 198 101 179 145 203
!
! 11 77 8 49
! 59 28 23 61
! 17 31 79 32
! 68 29 41 37
!
!No. 2
! 105 181 77 82 193 198 101 145 179 203
!
! 11 8 77 49
! 17 79 31 32
! 59 23 28 61
! 68 41 29 37
!
!No. 3
! 105 181 179 101 203 145 193 77 198 82
!
! 28 59 61 23
! 77 11 49 8
! 29 68 37 41
! 31 17 32 79
!
!No. 4
! 105 181 179 203 101 145 193 198 77 82
!
! 28 61 59 23
! 29 37 68 41
! 77 49 11 8
! 31 32 17 79
LET t0=TIME
PUBLIC NUMERIC S !和（魔法数）
LET S=29^2+37^2+41^2+68^2
PRINT S
PUBLIC NUMERIC H(0 TO 500,4) !和Sを4つの平方数で表現する S=A^2+B^2+C^2+D^2、ただし、A＜B＜C＜D
MAT H=ZER
PUBLIC NUMERIC X !その個数
LET X=0
FOR A=0 TO S !A^2＜S/4
LET AA=A*A
IF 4*AA>S THEN EXIT FOR !これ以上は不適切な値である
FOR B=A+1 TO S
LET BB=B*B
IF AA+3*BB>S THEN EXIT FOR
FOR C=B+1 TO S
LET CC=C*C
IF AA+BB+2*CC>S THEN EXIT FOR
FOR D=C+1 TO S !S/4＜D^2
LET DD=D*D
IF AA+BB+CC+DD>S THEN EXIT FOR
IF AA+BB+CC+DD=S THEN !平方数の組(A,B,C,D)を表示する
LET X=X+1 !平方数の候補、その個数
LET H(X,1)=A
LET H(X,2)=B
LET H(X,3)=C
LET H(X,4)=D
PRINT X;" (";STR$(A);",";STR$(B);",";STR$(C);",";STR$(D);")"
END IF
NEXT D
NEXT C
NEXT B
NEXT A
IF X>10 THEN
!和S=8515を、4つの平方和で表す。この場合、212組ある。
!解は、この212個の組から縦・横・斜めの計10個を選んでうまく並べられたものである。
!
!212個の組から10個を選ぶとき、16個の数値はすべて異なるものである。
!
!解の場合、(77,82,101,105,145,179,181,193,198,203)である。
!実際の数値の並びは、
! 11 77 8 49 | 77
! 59 28 23 61 | 179
! 17 31 79 32 | 145
! 68 29 41 37 | 198
! ----+-------------------+
! 181 101 193 82 203 105
!である。
PUBLIC NUMERIC F(0 TO 100) !数値の使用回数
PUBLIC NUMERIC Q1(4),Q2(4) !2つの斜めの数値の並べ方
PUBLIC NUMERIC R(10) !組10個を選ぶ
PUBLIC NUMERIC M(16) !魔方陣 4x4
PUBLIC NUMERIC Z !解の数
LET Z=0
!●条件 斜めの2つを選ぶ。8個の数値はすべて異なる。
!H(R(1),*)={A,B,C,D}、H(R(2),*)={E,F,G,H}とすると、
! A * * E
! * B F *
! * G C *
! H * * D
FOR i=1 TO X-1 !高々C(X,2)通り
MAT F=ZER
FOR u=1 TO 4
LET F(H(i,u))=1
NEXT u
LET R(1)=i !1つ目を組iとする
DIM W(0 TO 100) !save it
MAT W=F
FOR j=i+1 TO X
FOR u=1 TO 4
LET t=H(j,u)
IF F(t)=1 THEN EXIT FOR
LET F(t)=1
NEXT u
IF u>4 THEN !異なる8個の数の並びなら
LET R(2)=j !1つ目を組jとする
PRINT i;j; Z !debug ←←←←←
FOR u=0 TO FACT(4)-1 !(4!/2)通り
CALL Num2PermFactorial(u, Q1,4)
IF Q1(1)<Q1(4) THEN !※対称性を除く
LET M(1)=H(i,Q1(1)) !仮に置いてみる
LET M(6)=H(i,Q1(2))
LET M(11)=H(i,Q1(3))
LET M(16)=H(i,Q1(4))
FOR v=0 TO FACT(4)-1 !(4!/2)通り
CALL Num2PermFactorial(v, Q2,4)
IF Q2(1)<Q2(4) THEN !※対称性を除く
LET M(4)=H(j,Q2(1)) !仮に置いてみる
LET M(7)=H(j,Q2(2))
LET M(10)=H(j,Q2(3))
LET M(13)=H(j,Q2(4))
! 1 * * 4 ← 1行目
! * 6 7 *
! * 10 11 *
! 13 14 15 16
CALL try1row(1, M(1),M(4)) !1行目へ
END IF
NEXT v
END IF
NEXT u
END IF
MAT F=W !restore it
NEXT j
NEXT i
END IF
PRINT "実行時間=";TIME-t0
END
EXTERNAL SUB try1row(p, s1,s2) !バックトラック法で検索する（1行目） 高々210*(2!)通り
DIM W(0 TO 100) !save it
MAT W=F
FOR i=1 TO X !組が重複しないようにする
FOR u=1 TO p+2-1
IF i=R(u) THEN EXIT FOR
NEXT u
IF u>p+2-1 THEN
LET tt=0
FOR u=1 TO 4 !この「数値」を含む必要がある
LET t=H(i,u)
IF (t=s1 OR t=s2) THEN LET tt=tt+1
NEXT u
IF tt=2 THEN
!●条件 「3箇所現れる数」が8個、「2箇所現れる数」が8個となる。
! 数値の発生分布
! 3223 ← 1行目
! 2332
! 2332
! 3223
FOR u=1 TO 4
LET t=H(i,u)
LET F(t)=F(t)+1
IF F(t)>3 THEN EXIT FOR
NEXT u
IF u>4 THEN
LET R(p+2)=i !組iとする
LET t2=0 !2数を切り出して、並べ替える
FOR u=1 TO 4
LET t=H(i,u)
IF NOT(t=s1 OR t=s2) THEN
IF t2=0 THEN
LET A=t
LET t2=1
ELSE
LET B=t
END IF
END IF
NEXT u
LET M(2)=A
LET M(3)=B
CALL try2col(p+1, M(2),M(6),M(10)) !2列目へ
LET M(2)=B !swap it
LET M(3)=A
CALL try2col(p+1, M(2),M(6),M(10)) !2列目へ
END IF
MAT F=W !restore it
END IF
END IF
NEXT i
END SUB
EXTERNAL SUB try2col(p, s1,s2,s3) !バックトラック法で検索する（2列目） 高々209通り
DIM W(0 TO 100) !save it
MAT W=F
FOR i=1 TO X !組が重複しないようにする
FOR u=1 TO p+2-1
IF i=R(u) THEN EXIT FOR
NEXT u
IF u>p+2-1 THEN
LET tt=0
FOR u=1 TO 4 !この「数値」を含む必要がある
LET t=H(i,u)
IF (t=s1 OR t=s2 OR t=s3) THEN
LET tt=tt+1
ELSE
LET V=t
END IF
NEXT u
IF tt=3 THEN
FOR u=1 TO 4 !●条件 「3箇所現れる数」が8個、「2箇所現れる数」が8個となる。
LET t=H(i,u)
LET F(t)=F(t)+1
IF F(t)>3 THEN EXIT FOR
NEXT u
IF u>4 THEN
LET R(p+2)=i !組iとする
LET M(14)=V
CALL try3col(p+1, M(3),M(7),M(11)) !3列目へ
END IF
MAT F=W !restore it
END IF
END IF
NEXT i
END SUB
EXTERNAL SUB try3col(p, s1,s2,s3) !バックトラック法で検索する（3列目） 高々208通り
DIM W(0 TO 100) !save it
MAT W=F
FOR i=1 TO X !組が重複しないようにする
FOR u=1 TO p+2-1
IF i=R(u) THEN EXIT FOR
NEXT u
IF u>p+2-1 THEN
LET tt=0
FOR u=1 TO 4 !この「数値」を含む必要がある
LET t=H(i,u)
IF (t=s1 OR t=s2 OR t=s3) THEN
LET tt=tt+1
ELSE
LET V=t
END IF
NEXT u
IF tt=3 THEN
FOR u=1 TO 4 !●条件 「3箇所現れる数」が8個、「2箇所現れる数」が8個となる。
LET t=H(i,u)
LET F(t)=F(t)+1
IF F(t)>3 THEN EXIT FOR
NEXT u
IF u>4 THEN
LET R(p+2)=i !組iとする
LET M(15)=V
CALL try4row(p+1, M(13),M(14),M(15),M(16)) !4行目へ
END IF
MAT F=W !restore it
END IF
END IF
NEXT i
END SUB
EXTERNAL SUB try4row(p, s1,s2,s3,s4) !バックトラック法で検索する（4行目） 高々207通り
DIM W(0 TO 100) !save it
MAT W=F
FOR i=1 TO X !組が重複しないようにする
FOR u=1 TO p+2-1
IF i=R(u) THEN EXIT FOR
NEXT u
IF u>p+2-1 THEN
LET tt=0
FOR u=1 TO 4 !この「数値」を含む必要がある
LET t=H(i,u)
IF NOT(t=s1 OR t=s2 OR t=s3 OR t=s4) THEN EXIT FOR
LET tt=tt+1
NEXT u
IF tt=4 THEN
FOR u=1 TO 4 !●条件 「3箇所現れる数」が8個、「2箇所現れる数」が8個となる。
LET t=H(i,u)
LET F(t)=F(t)+1
IF F(t)>3 THEN EXIT FOR
NEXT u
IF u>4 THEN
LET R(p+2)=i !組iとする
CALL try1col(p+1, M(1),M(13)) !1列目へ
END IF
MAT F=W !restore it
END IF
END IF
NEXT i
END SUB
続く
|
|