山中さんへお礼と感想

 投稿日:2008年11月 2日(日)23時33分46秒
  再度の掲載ありがとうございます。
例の数字:1,1,1,4,56,9408・・・とはどうやって決まっているんだろう?
なにか公式でもあるのかしら、と疑問に思っていましたがつまりこれは実際に構成
したときに、この数しか作れないというものなのですね。
これは計算から求まる値ではないですよね。
このプログラムではっきりとその数の意味するものを理解できました。
 N=1、1=1!×0!×1
 N=2、2=2!×1!×1
 N=3、12=3!×2!×1
 N=4、576=4!×3!×4
 N=5、161,280=5!×4!×56
 N=6、812,851,200=6!×5!×9,408
 N=7、6,147,941,990,400=7!×6!×16,942,080
の計算からN=6では8億以上の組み合わせを調査せねばならないということに
なるわけですか?
本によると、6次のオイラー方陣が不可能であることを理論ではなく、場合列挙の
方法で証明した(1900年頃G.TARRYという人物)と書かれていました。
当時高速コンピューターもない時代にこんなことができるんでしょうか?
もしこんなに可能性が大量に発生する問題に計算機無しに決着をつけたとしたら
その根性はとんでもないものだと驚愕します。
先人の知恵や執念を垣間見た感慨です。
それにしてもオイラーという人物は、さらに怪物に見えます。
 

Re: 山中さんへお礼と感想

 投稿者:山中和義  投稿日:2008年11月 4日(火)13時38分41秒
  > No.43[元記事へ]

GAIさんへのお返事です。

C言語版を移植してみました。ただし、直訳ではありません。
全解求めるようになっていますので、C言語版のように最初の解のみは、
プログラムの最後のSTOP文を有効にしてください。

N=5がすでに厳しいようです。100倍!?ぐらいの速さの差を感じます。
前回紹介したバックトラック法よりは良好です。


!オイラー方陣を求める

LET N=5 !大きさ N×N

!※N=1,2,3,4,5,6,7,…なら、1,1,1,4,56,9408,16942080,…となる。
PUBLIC NUMERIC LM(9408,0 TO 35) !標準形ラテン方陣 N=6

PUBLIC NUMERIC CntOfLM !その数
LET CntOfLM=0

DIM M(0 TO N*N-1) !平方の方陣
MAT M=(-1)*CON
FOR i=0 TO N-1 !標準形 ※1行目と1列目が整列している
   LET M(i*N+0)=i
   LET M(0*N+i)=i
NEXT i

LET t0=TIME
CALL BackTrack(N,M,0) !左上から
PRINT CntOfLM
PRINT "計算時間=";TIME-t0



LET t0=TIME

PUBLIC NUMERIC ANSWER_COUNT !解答数
LET ANSWER_COUNT=0

LET cnt=0 !検証回数
LET cc=comb(CntOfLM+2-1,2)

DIM A(0 TO N-1,0 TO N-1),B(0 TO N-1,0 TO N-1)
FOR i=1 TO CntOfLM !標準形Aと標準形Bの展開との重複組合せ 56H2
   FOR y=0 TO N-1 !Aを指定する
      FOR x=0 TO N-1
         LET A(y,x)=LM(i,y*N+x)
      NEXT x
   NEXT y

   FOR j=i TO CntOfLM

      LET cnt=cnt+1 !進捗
      PRINT cnt;"/";cc

      FOR y=0 TO N-1 !Bを指定する
         FOR x=0 TO N-1
            LET B(y,x)=LM(j,y*N+x)
         NEXT x
      NEXT y

      DIM R(N) !順列の初期値
      FOR k=1 TO N
         LET R(k)=k
      NEXT k
      CALL RPerm(N,A,B, R,2) !まず行順を指定する ※1行目は固定
   NEXT j
NEXT i
IF ANSWER_COUNT=0 THEN PRINT "解なし"

PRINT "計算時間=";TIME-t0


END


EXTERNAL SUB BackTrack(N,M(),p) !(左上からの連番)位置pを調査する
IF p<N*N THEN !すべてが埋まるまで
   IF M(p)>=0 THEN !既に置いてあれば
      CALL BackTrack(N,M,p+1) !次へ
   ELSE
      FOR k=0 TO N-1 !数字0~N-1を
         CALL CheckRule(N,M, p,k, rc)!矛盾なく置ければ
         IF rc=1 THEN
            LET M(p)=k !ここに置いてみる
            CALL BackTrack(N,M,p+1) !次へ
            LET M(p)=-1 !取り消す
         END IF
      NEXT k
   END IF

ELSE !すべて埋まったら
   LET CntOfLM=CntOfLM+1 !数と配置を記録する
   FOR i=0 TO N*N-1
      LET LM(CntOfLM,i)=M(i)
   NEXT i

END IF
END SUB


EXTERNAL SUB CheckRule(N,M(), p,K, rc) !同じ数があるかどうか確認する
LET rc=0

LET row=INT(p/N) !行と列に換算する
LET col=MOD(p,N)

FOR i=0 TO row-1 !列
   IF M(i*N+col)=K THEN EXIT SUB
NEXT i

FOR i=0 TO col-1 !行
   IF M(row*N+i)=K THEN EXIT SUB
NEXT i

LET rc=1 !見つからないので、OK!
END SUB


EXTERNAL SUB RPerm(N,A(,),B(,), P(),i) !順列を生成して行の並び替え ※辞書式順ではない
IF I<N THEN
   FOR j=i TO N
      LET t=P(i) !i番目とj番目を交換する
      LET P(i)=P(j)
      LET P(j)=t
      CALL RPerm(N,A,B, P,i+1) !再帰呼出し
      LET t=P(i) !元に戻す
      LET P(i)=P(j)
      LET P(j)=t
   NEXT j

ELSE !完了なら
   DIM C(N) !順列の初期値
   FOR j=1 TO N
      LET C(j)=j
   NEXT j
   CALL CPerm(N,A,B,P,C,1) !今度は列順を指定する

END IF
END SUB


EXTERNAL SUB CPerm(N,A(,),B(,),R(), P(),i) !順列を生成して列の並び替え ※辞書式順ではない
IF I<N THEN
   FOR j=i TO N
      LET t=P(i) !i番目とj番目を交換する
      LET P(i)=P(j)
      LET P(j)=t
      CALL CPerm(N,A,B,R, P,i+1) !再帰呼出し
      LET t=P(i) !元に戻す
      LET P(i)=P(j)
      LET P(j)=t
   NEXT j

ELSE !オイラー方陣をつくって検証する

   DIM EM(N,N) !使用できる数字の組と使用状況
   MAT EM=ZER

   !※ラテン方陣の組合せなので、行と列の重複はない。
   FOR i=0 TO N-1 !方陣全体で同じ数があるかどうか確認する
      FOR j=0 TO N-1
         LET rr=A(i,j)+1 !オイラー方陣をつくる
         LET cc=B(R(i+1)-1,P(j+1)-1)+1
         IF EM(rr,cc)=1 THEN EXIT SUB !その数字は使用中なのでNG!
         LET EM(rr,cc)=1
      NEXT j
   NEXT i


   LET ANSWER_COUNT=ANSWER_COUNT+1 !解答数
   PRINT ANSWER_COUNT

   FOR i=0 TO N-1 !答えを表示する
      FOR j=0 TO N-1
         PRINT (A(i,j)+1)*10 + B(R(i+1)-1,P(j+1)-1)+1 ;
      NEXT j
      PRINT
   NEXT i

   !!!STOP !最初に見つけた答え

END IF
END SUB
 

戻る