平方魔方陣への挑戦

 投稿者:GAI  投稿日:2012年 2月22日(水)11時27分53秒
  > > A^2  B^2  C^2
> > D^2  E^2  F^2
> > G^2  H^2  I^2
> > の計算で魔方陣となる配列がとれるか探せるものでしょうか?
>
> 汎用的には、バックトラック法で解決します。
> 和をSとして、0≦A,B,C≦Sがおおざっぱな候補ですが、
> 1行目は、A^2+B^2+C^2=Sですから、
> Aは、A^2≦S
> Bは、A^2+B^2≦S
> Cは、A^2+B^2+C^2=S
> を満たさないといけません。

以前このヒントを頂き、これを4×4の平方魔方陣して

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年にオイラーがラグランジュへ教えたの記事を見る。)
の組合せをコンピュータで見つけ出そうとプログラムを4×4用に変更し、三日三晩走らせ続けましたが、いつ果てるかわからない計算をし続けるばかりで、一向に求めたい組合せをはじき出す様子がありません。

この解を求めるためには、なにか別の工夫や使える定理などがあるのでしょうか?

さらに調べものをしていましたら、

25^2  45^2  15^2  14^2  44^2   5^2  20^2

16^2  10^2  22^2   6^2  46^2  26^2  42^2

48^2   9^2  18^2  41^2  27^2  13^2  12^2

34^2  37^2  31^2  33^2   0^2  29^2   4^2

19^2   7^2  35^2  30^2   1^2  36^2  40^2

21^2  32^2   2^2  39^2  23^2  43^2   8^2

17^2  28^2  47^2   3^2  11^2  24^2  38^2

(0^2から48^2まで連続する整数の平方で構成されている。)
などが見つかっており、これはいったいコンピュータの仕事で可能なのかと不思議に感じてしまいます。

 

Re: 平方魔方陣への挑戦

 投稿者:山中和義  投稿日:2012年 3月 6日(火)15時43分14秒
  > No.1776[元記事へ]

GAIさんへのお返事です。

> 4×4の平方魔方陣して
>
> 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通り
で確認しています。


!平方数による4×4魔方陣

!実行結果
!
!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


続く
 

Re: 平方魔方陣への挑戦

 投稿者:山中和義  投稿日:2012年 3月 6日(火)15時44分43秒
  > No.1804[元記事へ]

続き


!同様に

EXTERNAL SUB try1col(p, s1,s2) !バックトラック法で検索する(1列目) 高々206*(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

         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 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(5)=A
            LET M(9)=B
            CALL try2row(p+1, M(5),M(6),M(7)) !2行目へ

            LET M(5)=B !swap it
            LET M(9)=A
            CALL try2row(p+1, M(5),M(6),M(7)) !2行目へ

         END IF
         MAT F=W !restore it
      END IF

   END IF
NEXT i
END SUB


EXTERNAL SUB try2row(p, s1,s2,s3) !バックトラック法で検索する(2行目) 高々205通り
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(8)=V
            CALL try3row(p+1, M(9),M(10),M(11)) !3行目へ

         END IF
         MAT F=W !restore it
      END IF

   END IF
NEXT i
END SUB

EXTERNAL SUB try3row(p, s1,s2,s3) !バックトラック法で検索する(3行目) 高々204通り
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(12)=V
            CALL try4col(p+1, M(4),M(8),M(12),M(16)) !4列目へ

         END IF

      END IF

   END IF
NEXT i
END SUB

EXTERNAL SUB try4col(p, s1,s2,s3,s4) !バックトラック法で検索する(4列目) 高々203通り
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

         LET R(p+2)=i !組iとする

         !--------------------
         LET Z=Z+1 !結果を表示する
         PRINT "No.";Z

         MAT PRINT R; !組

         FOR j=1 TO 16 !魔方陣 4x4
            PRINT M(j);
            IF MOD(j,4)=0 THEN PRINT
         NEXT j
         !--------------------

      END IF

   END IF
NEXT i
END SUB



!n!の順列パターン ⇔ 0~(n!-1)の番号

EXTERNAL SUB Num2PermFactorial(h, A(),N) !番号から順列パターンを生成する ※辞書式順序
LET v=h !非負の10進数整数を階乗進数へ
FOR j=1 TO N
   LET t=INT(v/j)
   LET A(N-j+1)=v-t*j +1 !階乗進数の各桁の値+1 A[1..N]=(N-1)! … 3! 2! 1! 0!
   LET v=t
NEXT j
FOR j=N-1 TO 1 STEP -1 !順列パターンへ
   FOR k=j+1 TO N
      IF A(k)>=A(j) THEN LET A(k)=A(k)+1
   NEXT k
NEXT j
END SUB

 

戻る