プログラムのお願い

 投稿日：2008年11月 1日(土)10時51分27秒
  オイラー方陣が６次では構成不可能であることを、しらみつぶしにより
確認することをやってみたいのです。
どなたか十進BASICにてプログラムを組んでいただけないでしょうか？
オイラー方陣とは5次なら（２次と６次以外は構成可能と証明されている。）
12 23 34 45 51
53 14 25 31 42
44 55 11 22 33
35 41 52 13 24
21 32 43 54 15
のように、十位と一位にくる数（１～５）が
各行、各列に重複することが起きない。
（ただし２５個の数字は全て異なるものとする。）
自分でやっていて、なかなか進展しないものですのでよろしくお願いします。 		 

Re: プログラムのお願い

 投稿日：2008年11月 1日(土)20時58分48秒
  > No.37[元記事へ]

1～6の数字で作られる2桁の数は全部で36個あります。
なので，これら36個の数の順列すべてについて条件を満たすかどうか調べればよいはずです。
ただし，
36!＝371993326789901217467999448150835200000000 ≒3.7E41
なので，1秒に1万件テストしたとしても3.7E37秒≒1.12E30年かかります。 		 

Re: プログラムのお願い

 投稿日：2008年11月 1日(土)22時13分32秒
  > No.38[元記事へ]

白石　和夫さんへのお返事です。
/* ６次のオイラー方陣が存在しないことを確認する. */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 6

char lb[9408][N][N];
/* N=1～7: 1,1,1,4,56,9408,16942080 N=7は非現実的 */

int lbs;
char wb[N][N];
int p, q;
char xidx[N], yidx[N];

void check1(int n);

void makelb(int x, int y)
{
int i, j;

for(i = 0; i < N; ++i){
for(j = 0; j < x; ++j)
if((char)i == wb[y][j])
break;
if(j >= x){
for(j = 0; j < y; ++j)
if((char)i == wb[j][x])
break;
if(j >= y){
wb[y][x] = (char)i;
if(y == N - 1 && x == N - 1){
memcpy(lb[lbs++], wb, sizeof(wb));
return;
}
if(y == N - 1)
makelb(x + 1, 1);
else
makelb(x, y + 1);
}
}
}
}

void echk(void)
{
static char fb[N][N];
int i, j;

memset(fb, 0, sizeof(fb));
for(i = 0; i < N; ++i)
for(j = 0; j < N; ++j){
if(fb[lb[p][i][j]][lb[q][yidx[i]][xidx[j]]])
return;
fb[lb[p][i][j]][lb[q][yidx[i]][xidx[j]]] = 1;
}
for(i = 0; i < N; ++i)
for(j = 0; j < N; ++j)
printf("%c%c%c", lb[p][i][j] + '0', lb[q][yidx[i]][xidx[j]] + '0',
j == N - 1 ? '\n' : ' ');
exit(0);
}

void check2(int n)
{
int i;
char c;

for(i = n; i < N; ++i){
c = yidx[i];
yidx[i] = yidx[n];
yidx[n] = c;
if(yidx[n] != xidx[n] && (n != 1 || yidx[n] < xidx[n]))
if(n == N - 1)
echk();
else
check1(n + 1);
c = yidx[i];
yidx[i] = yidx[n];
yidx[n] = c;
}
}

void check1(int n)
{
int i;
char c;

for(i = n; i < N; ++i){
c = xidx[i];
xidx[i] = xidx[n];
xidx[n] = c;
check2(n);
c = xidx[i];
xidx[i] = xidx[n];
xidx[n] = c;
}
}

int main(void)
{
int i, count;

for(i = 0; i < N; ++i)
wb[0][i] = wb[i][0] = (char)i;
lbs = 0;
makelb(1, 1);

count = 0;
for(p = 0; p < lbs; ++p)
for(q = p; q < lbs; ++q){
if(++count % 1000 == 0)
printf("%d\r", count);
for(i = 0; i < N; ++i)
xidx[i] = yidx[i] = (char)i;
check1(1);
}
printf("解は見つかりませんでした.\n");
return 0;
}
がｃ言語でのプログラムでの解決法（５時間ほどでOK！）です。
これをBASICで書き直せないでしょうか。（自分はC言語に不勉強なので） 		 

Re: プログラムのお願い

 投稿者：山中和義  投稿日：2008年11月 2日(日)08時22分9秒
  > No.38[元記事へ]

総当りの王道としてバックトラック法があります。
ただし、不適以降は無視（枝刈り）するので検証する場合の数がいくらか減ります。

う～ん、現実的ではない！
掲載されたＣ言語のように標準形のラテン方陣からのアプローチを検討してほしい。


LET N=5 !大きさ N×N

PUBLIC NUMERIC ANSWER_COUNT !解答数
LET ANSWER_COUNT=0

PUBLIC STRING num$
LET num$="0123456789ABCDEF" !N進法の数字

DIM M(0 TO N-1,0 TO N-1) !平方の方陣
MAT M=(-1)*CON

SET WINDOW -1,N+1,N+1,-1
DRAW grid

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

END


EXTERNAL SUB BackTrack(N,M(,),p) !（左上からの連番）位置pを調査する
IF p<N*N THEN !すべてが埋まるまで
   LET row=INT(p/N) !行と列に換算する
   LET col=MOD(p,N)

   FOR k=0 TO N*N-1 !０～N*N-1範囲の数字を
      CALL CheckRule(N,M, row,col,k, rc)!矛盾なく置ければ
      IF rc=1 THEN
         SET TEXT COLOR 1
         PLOT TEXT ,AT col+0.5,row+0.5: STR$(k)

         LET M(row,col)=k !ここに置いてみる
         CALL BackTrack(N,M,p+1) !次へ
         LET M(row,col)=-1 !取り消す

         SET TEXT COLOR 0
         PLOT TEXT ,AT col+0.5,row+0.5: STR$(k)
      END IF
   NEXT k

ELSE !すべて埋まったら
   LET ANSWER_COUNT=ANSWER_COUNT+1 !解答数
   PRINT ANSWER_COUNT

   FOR i=0 TO N-1
      FOR j=0 TO N-1
         LET t=M(i,j)
         LET k1=MOD(t,N)+2 !N進法での各桁の値（文字位置を加味）
         LET k2=INT(t/N)+2
         PRINT num$(k2:k2); num$(k1:k1); " "; !解を表示する
      NEXT j
      PRINT
   NEXT i
   PRINT

END IF
END SUB


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

FOR y=0 TO N-1 !埋まっている範囲で未使用の数字か
   FOR x=0 TO N-1
      IF y>=row AND x>=col THEN EXIT FOR
      IF M(y,x)=K THEN EXIT SUB !見つかったので、ＮＧ！
   NEXT x
NEXT y

LET k1=MOD(K,N) !N進法での１桁目
LET k2=INT(K/N) !N進法での２桁目
FOR y=0 TO row-1 !列
   LET t=M(y,col)
   IF MOD(t,N)=k1 THEN EXIT SUB
   IF INT(t/N)=k2 THEN EXIT SUB
NEXT y

FOR x=0 TO col-1 !行
   LET t=M(row,x)
   IF MOD(t,N)=k1 THEN EXIT SUB
   IF INT(t/N)=k2 THEN EXIT SUB
NEXT x

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

Re: プログラムのお願い

 投稿日：2008年11月 2日(日)13時12分5秒
  > No.40[元記事へ]

山中和義さんへのお返事です。

まさにこんなことができるプログラムを構成したかったのです。
自分だけであくせく路頭に迷うより、誰かに尋ねると世の中
才能ある人が必ずいるもので、こちらが１ヶ月かかってもできない
ことでも、１時間もあれば見通せる人がいるなんて感動です。
プログラムをコピーさせてもらい、中身の仕組みを分析していきます。
どうも自分はコンピューターに使われている感覚ですが、
山中さんのような人はまさにコンピューターをこき使っている雰囲気です。
私も、コンピューターを思いのまま動かすことが出来るプログラム構成の
力を向上できるよう精進していきたいです。
山中さんは趣味でやられてきたのですか？
それともお仕事で必要でマスターされてきたのですか？
できたらコンピューター歴をお聞かせください。 		 

Re: プログラムのお願い

 投稿者：山中和義  投稿日：2008年11月 2日(日)20時25分34秒
  > No.41[元記事へ]

GAIさんへのお返事です。

仕事と趣味でコンピュータは扱っています。
このBASICは高校数学、工業を題材にプログラミングを楽しんでいます。


●掲載のＣ言語プログラムの説明
ラテン方陣からのアプローチ
作業手順
Step1. 標準形ラテン方陣を求める。
　例. ３×３の場合
　　1 2 3
　　2 3 1
　　3 1 2
Step2. ２つのラテン方陣の組合せる。
　標準形ラテン方陣から対称、回転を含んですべてのラテン方陣を求める。
　オイラー方陣が成立するものを採用する。
　例. ３×３の場合
　　1 2 3　　3 1 2　　13 21 32
　　2 3 1　　2 3 1　　22 33 11
　　3 1 2　　1 2 3　　31 12 23
　オイラー方陣が成立するので、採用。

たとえば、３×３の場合は標準形が１通り、その展開が１２通りあるから
1Ｈ2×１２通りを検証する必要がある。

　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=1,2,3,4,5,6,7,…なら、1,1,1,4,56,9408,16942080,…となる。

方陣が大きくなればそれに伴い増大して容量、計算量が増える。


インタプリタ系言語BASICで処理を考えると、
容量の問題から掲載されたＣ言語の手順のように組合せごとに標準形ラテン方陣を展開したい。
でも、検証する「場合の数」が多いため、処理時間の問題から、ラテン方陣をそのまま記録したい。

これは悩ましい問題である。



!（標準形）ラテン方陣を求める

LET N=5 !大きさ N×N

PUBLIC NUMERIC CntOfLM !その数
LET CntOfLM=0

PUBLIC STRING num$
LET num$="0123456789ABCDEF" !N進法の数字

DIM M(0 TO N*N-1) !平方の方陣
MAT M=(-1)*CON

FOR i=0 TO N-1 !標準形の場合　※１行目と１列目が整列している
   LET M(i*N+0)=i
   LET M(0*N+i)=i
NEXT i

LET t0=TIME
CALL BackTrack(N,M,0) !左上から
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 !数字０～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 !解答数
   PRINT CntOfLM

   FOR i=0 TO N-1
      FOR j=0 TO N-1
         LET t=M(i*N+j)+1
         PRINT num$(t+1:t+1); " "; !解を表示する
      NEXT j
      PRINT
   NEXT i
   PRINT

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 !見つからないので、ＯＫ！
END SUB 		 

Re: プログラムのお願い

 投稿者：SECOND  投稿日：2008年11月 4日(火)14時32分41秒
  > No.39[元記事へ]

!掲示のＣ言語のリストを、十進BASIC版に書き直したもので、何も変わっていません。
!全く同じものだと、思います。違っていたら御免なさい。

!check1、check2 の交番する再帰コールは、見ずらいので、
!check1 １本の中に統合したが、内容は同じです。

OPTION BASE 0
LET N= 3 !　2,3,4,5,6
DIM lb(9408,N,N) !　N=1～7: 1,1,1,4,56,9408,16942080 N=7は非現実的
DIM wb(N,N), xidx(N), yidx(N), fb(N,N)
!
CALL main

SUB makelb(x, y)
   local i,j
   FOR i=0 TO N-1
      FOR j=0 TO x-1
         IF i=wb(y,j) THEN EXIT FOR ! break;
      NEXT j
      IF j>x-1 THEN
         FOR j=0 TO y-1
            IF i=wb(j,x) THEN EXIT FOR ! break;
         NEXT j
         IF j>y-1 THEN
            LET wb(y,x)= i
            IF y=N-1 AND x=N-1 THEN
            !----memcpy(lb[lbs++], wb, sizeof(wb));
               FOR a=0 TO N
                  FOR b=0 TO N
                     LET lb(lbs,a,b)=wb(a,b)
                  NEXT b
               NEXT a
               LET lbs=lbs+1
               !---------------
               EXIT SUB ! return;
            END IF
            IF y=N-1 THEN CALL makelb(x+1, 1) ELSE CALL makelb((x),y+1)
         END IF
      END IF
   NEXT i
END SUB


SUB echk
   local i,j
   MAT fb=ZER ! memset(fb, 0, sizeof(fb));
   FOR i= 0 TO N-1
      FOR j= 0 TO N-1
         IF fb( lb(p,i,j), lb(q,yidx(i),xidx(j)) )>0 THEN EXIT SUB ! return;
         LET fb( lb(p,i,j), lb(q,yidx(i),xidx(j)) )=1
      NEXT j
   NEXT i
   FOR i= 0 TO N-1
      FOR j= 0 TO N-1
         PRINT USING "%#": lb(p,i,j)+1, lb(q,yidx(i),xidx(j))+1;
         IF j=N-1 THEN PRINT ELSE PRINT " ";
      NEXT j
   NEXT i
   STOP ! exit(0);
END SUB


SUB check1(n_)
   local i
   FOR i=n_ TO N-1
      swap xidx(i),xidx(n_)
      !-----check2(n_)
      local i_
      FOR i_= n_ TO N-1
         swap yidx(i_),yidx(n_)
         IF ( yidx(n_)<>xidx(n_)) AND (n_<>1 OR yidx(n_)< xidx(n_) ) THEN
            IF n_=N-1 THEN CALL echk ELSE CALL check1(n_+1)
         END IF
         swap yidx(i_),yidx(n_)
      NEXT i_
      !------
      swap xidx(i),xidx(n_)
   NEXT i
END SUB


SUB main
   FOR i= 0 TO N-1
      LET wb(i,0)= i
      LET wb(0,i)= i
   NEXT i
   LET lbs = 0
   PRINT "N=";N; ! 追加した表示
   CALL makelb(1,1)
   PRINT "lbs=";lbs !追加
   MAT PRINT wb !　　追加
   LET count= 0
   FOR p=0 TO lbs-1
      FOR q=p TO lbs-1
         LET count=count+1
         IF MOD(count,1000)=0 THEN PRINT count
         FOR i= 0 TO N-1
            LET yidx(i)= i
            LET xidx(i)= i
         NEXT i
         CALL check1(1)
      NEXT q
   NEXT p
   PRINT "解は見つかりませんでした."
END SUB

END

!注意：このリストは、for~nextの中から再帰コールをしているので、十進BASICの
!　　　Ver7.2.0 以降 のバージョンが必要です。 		 

Re: プログラムのお願い

 投稿者：山中和義  投稿日：2008年11月 4日(火)16時27分16秒
  > No.45[元記事へ]

SECONDさんへのお返事です。

SECONDさん、お久しぶりです。

Ｃ言語版のコードをみて思ったのですが

・N=1が求まらない
・順列の生成がおかしい（行や列の交換が不十分）
　→標準形からすべて展開されていない
　→exitの箇所をコメント（無効）にしても全解が得られない
　→N=6で検証していない箇所がある
の疑問があります。

GAIさんを経由してＣ言語版の作者に聞くのが筋と思いますが、
SECONDさんは、どのように感じていますか？ 		 

Re: プログラムのお願い

 投稿者：SECOND  投稿日：2008年11月 4日(火)17時00分31秒
  > No.46[元記事へ]

山中和義さんへのお返事です。

全く同感です。その様にして頂ければと、思います。 		 

Re: プログラムのお願い

 投稿日：2008年11月 5日(水)22時07分8秒
  > No.46[元記事へ]

山中和義さんへのお返事です。

> Ｃ言語版のコードをみて思ったのですが
>
> ・N=1が求まらない
> ・順列の生成がおかしい（行や列の交換が不十分）
> 　→標準形からすべて展開されていない
> 　→exitの箇所をコメント（無効）にしても全解が得られない
> 　→N=6で検証していない箇所がある
> の疑問があります。


このことを製作者の方にお尋ねしましたところ、次のようなメールを頂きました。

・N=1が求まらない

  N=1に対処するとプログラムが面倒になるだけですので
無視しています（手間をかけてN=1にわざわざ対処しても、
まったく無意味ですよね？）。

> ・順列の生成がおかしい（行や列の交換が不十分）
> 　→標準形からすべて展開されていない
> 　→exitの箇所をコメント（無効）にしても全解が得られない
> 　→N=6で検証していない箇所がある

  おかしくないはずです。
  すべてを検証すると非常に長い時間がかかりますので、
数学的に考えて検証が必要ないものは省いています。
（省かないと、現実的な時間で求まりません。）

との回答でした。連絡まで 		 

Re: プログラムのお願い

 投稿者：山中和義  投稿日：2008年11月 6日(木)07時10分30秒
  > No.52[元記事へ]

GAIさんへのお返事です。

お手数おかけしました。ありがとうございます。 		 

戻る