３＊３の魔法陣

[gtdf]

３＊３の魔法陣の解を求めるプログラムです。
一応これで求まるのですが、for文を使いまくっていて、非常に汚いプログラムになってしまいました。
そして、実行にかなり時間がかかってしまいます。
再帰を使えばもっとすっきりすると思うんですが、どうやればいいか分かりません。
どうすればいいでしょうか。
以下にソースを載せます。

#include <stdio.h>

int main(void) {

 int i, j, k, l, m, n, o, p, q;
 int x;
 int a, b, c;
 int data[9];

 for (i=1; i<=9; i++) {
  data[0] = i;
  for (j=1; j<=9; j++) {
   data[1] = j;
   for (k=1; k<=9; k++) {
    data[2] = k;
    for (l=1; l<=9; l++) {
     data[3] = l;
     for (m=1; m<=9; m++) {
      data[4] = m;
      for (n=1; n<=9; n++) {
       data[5] = n;
       for (o=1; o<=9; o++) {
        data[6] = o;
        for (p=1; p<=9; p++) {
         data[7] = p;
         for (q=1; q<=9; q++) {
          data[8] = q;

          c = 0;
          for (a=0; a<9; a++) {
           for (b=a+1; b<9; b++) {
            if (data[a] == data)
             c++;
           }
          }
          if (c == 0) {
           if ((data[0] + data[1] + data[2]) ==
               (data[3] + data[4] + data[5]) &&
               (data[0] + data[1] + data[2]) ==
               (data[6] + data[7] + data[8]) &&
               (data[0] + data[1] + data[2]) ==
               (data[0] + data[3] + data[6]) &&
               (data[0] + data[1] + data[2]) ==
               (data[1] + data[4] + data[7]) &&
               (data[0] + data[1] + data[2]) ==
               (data[2] + data[5] + data[8]) &&
               (data[0] + data[1] + data[2]) ==
               (data[0] + data[4] + data[8]) &&
               (data[0] + data[1] + data[2]) ==
               (data[2] + data[4] + data[6]))
     {

               for (x=0; x<9; x++) {
                printf("%2d", data[x]);
                if (x == 2 || x == 5 || x == 8)
                 puts("");    
               }
               puts("");
           }
          }
         }
        }
       }
      }
     }
    }
   }
  }
 }
 printf("以上\n");
 return 0;
}

よろしくお願いします。

[gtdf]

すみません。[/pre]が抜けていました。

もう一度載せます。

#include <stdio.h>

int main(void) {

 int i, j, k, l, m, n, o, p, q;
 int x;
 int a, b, c;
 int data[9];

 for (i=1; i<=9; i++) {
  data[0] = i;
  for (j=1; j<=9; j++) {
   data[1] = j;
   for (k=1; k<=9; k++) {
    data[2] = k;
    for (l=1; l<=9; l++) {
     data[3] = l;
     for (m=1; m<=9; m++) {
      data[4] = m;
      for (n=1; n<=9; n++) {
       data[5] = n;
       for (o=1; o<=9; o++) {
        data[6] = o;
        for (p=1; p<=9; p++) {
         data[7] = p;
         for (q=1; q<=9; q++) {
          data[8] = q;

          c = 0;
          for (a=0; a<9; a++) {
           for (b=a+1; b<9; b++) {
            if (data[a] == data)
             c++;
           }
          }
          if (c == 0) {
           if ((data[0] + data[1] + data[2]) ==
               (data[3] + data[4] + data[5]) &&
               (data[0] + data[1] + data[2]) ==
               (data[6] + data[7] + data[8]) &&
               (data[0] + data[1] + data[2]) ==
               (data[0] + data[3] + data[6]) &&
               (data[0] + data[1] + data[2]) ==
               (data[1] + data[4] + data[7]) &&
               (data[0] + data[1] + data[2]) ==
               (data[2] + data[5] + data[8]) &&
               (data[0] + data[1] + data[2]) ==
               (data[0] + data[4] + data[8]) &&
               (data[0] + data[1] + data[2]) ==
               (data[2] + data[4] + data[6])
               )
                     {

               for (x=0; x<9; x++) {
                printf("%2d", data[x]);
                if (x == 2 || x == 5 || x == 8)
                 puts("");    
               }
               puts("");
           }
          }
         }
        }
       }
      }
     }
    }
   }
  }
 }
 printf("以上\n");
 return 0;
}

[Libra]

ぱっと見た感じですが、上のソースですと魔法陣の中の数字が
１、１、１、１、１、１、１、１、１→１、１、１、１、１、１、１、１、２・・・・

のように、１つずつ判定していってると思われます。
これだと、９の９乗回ループして計算している事になります。

しかし、魔法陣の中の数字は重複しないので、
最初から配列に１～９の数字を代入し
配列の中の数字を入れ替えて魔法陣の条件を満たすか判定した方が
重複判定をしなくてよい分、演算回数が少なくなるのではないでしょうか？
バブルソートに似た形をとると良いかも。

[gtdf]

早速の回答ありがとうございます。

無駄な処理をかなりしていることはわかっていて、ソートするという方法も思いついたのですが、
１～９の順列を生成する方法が思いつかず、断念しました。

１～９の順列を生成するにはどうすればよいのでしょうか。

よろしくお願いします。

[Libra]

順列を求めるプログラムに魔法陣の判定を入れるだけなので、
すぐ出来ると思います。

順列を求めるプログラムは「順列 C言語」「順列 プログラム」
などで検索すれば出てくると思いますよ。

順列のプログラムを自分で作ってみようと思いましたが、無理でした(汗)

[たいちう]

簡単な方法を紹介。

#include <stdio.h>

int a, b, c,
    d, f, g,
    e, h, i; // e, f, gの順番に注意

int main() {
    int sum;
    for (a = 1; a <= 9; a++) {
        for (b = 1; b <= 9; b++) {
            if (a == b) continue;
            for (c = 1; c <= 9; c++) {
                if (a == c || b == c) continue;
                sum = a + b + c;
                for (d = 1; d <= 9; d++) {
                    if (a == d || b == d || c == d) continue;
                    e = sum - a - d;
                    if (e < 1 || 9 < e) continue;
                    if (a == e || b == e || c == e || d == e) continue;
                    f = sum - c - e;
                    if (f < 1 || 9 < f) continue;
                    if (a == f || b == f || c == f || d == f || e == f) continue;
                    g = sum - d - f;
                    if (g < 1 || 9 < g) continue;
                    if (a == g || b == g || c == g || d == g || e == g || f == g) continue;
                    h = sum - b - f;
                    if (h < 1 || 9 < h) continue;
                    if (a == h || b == h || c == h || d == h || e == h || f == h || g == h) continue;
                    i = sum - a - f;
                    if (i < 1 || 9 < i) continue;
                    if (a == i || b == i || c == i || d == i || e == i || f == i || g == i || h == i) continue;
                    if (c + g + i != sum) continue;
                    if (e + h + i != sum) continue;

                    if (a > c || a > e || c > e) continue; // これはなくてもよい 

                    printf("    %d %d %d\n", a, b, c);
                    printf("    %d %d %d\n", d, f, g);
                    printf("    %d %d %d\n", e, h, i);
                    printf("\n");
                }
            }
        }
    }

    // quit
    printf("End.\n");
    getchar();
    return 0;
}

[gtdf]

順列のプログラムを見てみたのですが・・・

よくわかりませんでした・・・
（もう少し考えてみます）

上述したソースを再帰を使って書いたらどうなるのでしょうか。

[gtdf]

たいちうさん、回答ありがとうございます。

なんか、すごいプログラムですね。
自分では、まず思いつけません。

なぜ、e,f,gの並びがあのようになるのでしょうか。
そして、なぜ、sumでa,b,cの和をとっているのでしょうか。

３＊３の魔法陣にはそういった性質があり、それをもとにプログラムを作ったのでしょうか。

[Libra]

>たいちうさん

総当たりではなく、人間が解く時に近い方法ですね。流石です！

＞gtdfさん
上述したソースを仮に再帰に書き換えても、
元となるアルゴリズム自体に変更がなければ
変わらないと思います。


計算量だと

重複を許した総当たり＞重複無しの順列総当たり＞たいちうさんの方法になりますね。



３×３の魔方陣の和は１５で、入る数字は１～９というルールで、
例えばａとｂに１と２が入った時、この時点で魔方陣不成立ですよね。
sumにaとbとcの和、ｄに何か値を入れた時、eの値が決定します。
sumの値が正しくないと、eの値が負の数や１０以上になったりします。


この時、総当たりだと、
「この時点で不成立だけど、残りも一応やらないとなぁ・・・」

という感じで、不成立でも全部のパターンが当てはまるかの判定を行います。

たいちうさんの方法だと、
「あ～、もう最初っから魔方陣不成立だ、次いこ次！」

と言って、以下のパターンの判定処理を飛ばすことが出来るのです。

[フリオ]

　
　1~9の魔方陣の場合、

列の合計は、15になります。

5と同じ列の2つの数字の合計は10です。
合計が10になる組み合わせは、(1,9)(2,8)(3,7)(4,6)の4つなので、
5は必ず中央になります。

1と同じ列の2つの数字の合計は14です。
合計が14になる組み合わせは、(5,9)(6,8)の2つなので、
1は各辺の真中のどこかになります。

3と同じ列の2つの数字の合計は12です。
合計が12になる組み合わせは、(4,8)(5,7)の2つなので、
3は1と同列でない各辺の真中のどこかになります。

足して10になるのは、1は9、3は7なので、各辺の真中は奇数になります。

残りの2、4、6、8は4隅に入ります。

2と1、2と3、4と1、が同列になることは有りません。

一方の縦横の辺が決定すれば、もう一方の縦横も決定します。

これらの条件を適当に組み合わせて、こんな感じでどうでしょう。
　
　

#include <stdio.h>

#define Swap(a, b) {int c = a; a = b; b = c;}

int Is_Magic_Sqr(int a[/url])
{
    int i;
    
    if(a[4] != 5) return 0;
    for(i = 0; i < 4; ++ i){
        if(i & 1 && !(a & 1) || !(i & 1) && a & 1) return 0;
        if(a + a[8 - i] != 10) return 0;
    }
    if(a[0] + a[1] + a[2] != 15 || a[0] + a[3] + a[6] != 15) return 0;
    return 1;
}

void Print(int a[/url])
{
    int i;
    
    for(i = 0; i < 9; ++ i){
        printf("%d ", a);
        if(i % 3 == 2) putchar('\n');
    }
    putchar('\n');
}

void Magic_Sqr(int a[/url], int n, int m)
{
    int i;
    
    if(m + 1 == n){
        if(Is_Magic_Sqr(a)) Print(a);
        return;
    }
    for(i = m; i < n; ++ i){
        Swap(a[m], a);
        Magic_Sqr(a, n, m + 1);
        Swap(a[m], a);
    }
}

int main(void)
{
    int a[/url] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    Magic_Sqr(a, 9, 0);
    return 0;
}

　

[gtdf]

＞Libraさん
ありがとうございます。おかげで、たいちうさんのプログラムが理解できました。
確かに、いわれてみればそうですね。a,b,c,dの値が決まったら、eがわかり、
それがわかれば、fがわかる・・・という感じで決まりますね。

＞フリオさん
回答ありがとうございます。
プログラムで分からないことがあります・・・

if(i & 1 && !(a & 1) || !(i & 1) && a & 1) return 0;

の、i & 1 や　!(a & 1) といったものは一体何を表しているのでしょうか。

また、Magic_Sqr関数が分かりません・・・
再帰が入ると途端にわからなくなってしまいます・・・
結局、Magic_Sqe関数は何をしているのでしょうか。

[フリオ]

　
if(i & 1 && !(a & 1) || !(i & 1) && a & 1) return 0;
は、
if((i & 1) != (a & 1)) return 0;

if(a[0] + a[1] + a[2] != 15 || a[0] + a[3] + a[6] != 15) return 0;
return 1;
は、
return a[0] + a[1] + a[2] == 15 && a[0] + a[3] + a[6] == 15;

に変更します。


>i & 1 や　!(a & 1) といったものは一体何を表しているのでしょうか。

　& は、各ビットの論理積、
! は、論理否定で、!a は、a == 0 と同じです。
演算子を調べてみてください。


Magic_Sqr関数は、1~9の順列を生成し、Is_Magic_Sqr関数で判定、Print関数で表示してます。
　

[フリオ]

　
　5は固定なので、順列からはずしました。
後、細かい部分も変更してますが、考え方は同じです。
　

#include <stdio.h>

#define Swap(a, b) {int c = a; a = b; b = c;}

int Is_Magic_Sqr(int a[/url])
{
    int i;
    
    for(i = 0; i < 4; ++ i){
        if((i & 1) != (a & 1) || a + a[7 - i] != 10) return 0;
    }
    return a[0] + a[1] + a[2] == 15 && a[0] + a[3] + a[5] == 15;
}

void Magic_Sqr(int a[/url], int m)
{
    int i;
    
    if(m == 7){
        if(Is_Magic_Sqr(a)){
            printf("%d %d %d\n%d 5 %d\n%d %d %d\n\n",
                a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
        }
        return;
    }
    for(i = m; i <= 7; ++ i){
        Swap(a[m], a);
        Magic_Sqr(a, m + 1);
        Swap(a[m], a);
    }
}

int main(void)
{
    int a[/url] = {1, 2, 3, 4, 6, 7, 8, 9};
    
    Magic_Sqr(a, 0);
    return 0;
}

　

[gtdf]

＞フリオさん
すみません。やはり、

for(i = m; i <= 7; ++ i){
    Swap(a[m], a);
    Magic_Sqr(a, m + 1);
    Swap(a[m], a);
}

の部分が理解できません・・・

なぜ、これで、順列が生成できるのでしょうか。
再帰があると頭が混乱してしまいます。

[dic]

横からすいません
5は必ず中央にくるというのが気になって
組んでみました

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

int    gi[256];
int    gj[256];
int    gk[256];
int    gp;

//    合計で１５になる組み合わせを求める
void    get15( int *out, int *use )
{
    int    i,j,k;
    int    temp;
    for( i=0; i<9; i++ )
    {
        for( j=i+1; j<9; j++ )
        {
            for( k=j+1; k<9; k++ )
            {
                temp = use + use[j] + use[k];
                if( temp == 15 ){
                    printf( "%d %d %d\n", use, use[j], use[k] );
                    gi[gp] = i;
                    gj[gp] = j;
                    gk[gp] = k;
                    gp++;
                }
            }
        }
    }
}

int main(void)
{
    int    magic[9];
    int    number[9] = { 1,2,3,4,5,6,7,8,9 };

    memset( gi, 0, sizeof(gi) );
    memset( gj, 0, sizeof(gj) );
    memset( gk, 0, sizeof(gk) );
    gp = 0;

    get15( magic, number );

    printf( "１５になる組み合わせの数:%d\n", gp );

    return 0;
}

で、実行結果が
1 5 9
1 6 8
2 4 9
2 5 8
2 6 7
3 4 8
3 5 7
4 5 6
１５になる組み合わせの数:8
となり８パターンみたいですが、どこか間違ってますかね？
再帰使ってないです・・・すいません

この組み合わせで、空白を埋めていくという方法を取りたかったのでが
わからないです・・・

[組木紙織]

８パターンは多分間違ってないと思います。

5が必ず中央にくるというのは、(代数的に計算してもいいんですが)
その8パターンのうち5を含んだパターンはいくつありますか？
ほかの数を含んだパターンより多いはずです。

３×３の正方形の魔法陣の真ん中の数は少なくとも4つのパターンに含まれてないといけないです。
(縦、横、斜め*2パターン)
これを満たす数が5なので、真ん中にくる数は5のみになります。

[gtdf]

質問者ですが・・・

８パターンは、間違っていません。
（縦３つ、横３つ、斜め２つ）
一応、正しい魔方陣を載せておきます。

８３４
１５９
６７２

[sizuma]

たいちうさんのプログラムまでしか読んでませんが、アルゴリズムとしては十分見やすいんでこれで十分だと思いますよ？

わざわざ自分が見て理解し難い再帰を使う必要はないと思います。
別に効率がよくなるわけではないし。
もちろんわかりやすくなる場面で使えるようになることは大切だと思います。
と考えると、再帰で書いたコードとそうでないコードを見比べてみるのも大事でしょうけどね。

gtgfさんのコードだと、3*3の魔方陣の解は1パターンでよいのではしょうか。
見つけたらgotoで抜け出して、あとは表示のパターンを変えて表示すればいいと。
数字は見つけたパターンの添え字です。

123
456
789
上と下の行を交換
789
456
123
一番上の行列の転置行列（つまりｘとyの添え字を交換したもの）
147
258
369
同じく上と下を交換
369
258
147
残りは上下を交換したものについての転置行列と、それぞれ上と下の行を交換したものを表示させれば全パターンいけそうです。
たいちうさんのコードで残り全部の配置パターンを見つけるよりも早く終わるでしょう。
4＊4じゃぁ完璧に書き換えなきゃいけなくなるけど・・・

[たいちう]

sizuma さん

> gtgfさんのコードだと、3*3の魔方陣の解は1パターンでよいのではしょうか。
> 見つけたらgotoで抜け出して、あとは表示のパターンを変えて表示すればいいと。

予め正解の数が分からない場合、全ての解を見つける方が好ましいと思います。
問題の性質にもよりますが。

例えば「3*3の魔方陣の解を全て求めよ。対称解も別解とする。」という問題の場合、
「1つ見つけて8通りの表示をして終了するプログラム」でも8つの解を表示できます。
しかしそれ以上存在しないことを、何らかの方法で示す必要が生じます。

[sizuma]

＞予め正解の数が分からない場合、全ての解を見つける方が好ましいと思います
確かにそうですね。

＞3*3の魔方陣の解を全て求めよ。対称解も別解とする
こう問題を提示されれば考え易いんですけどね。
僕は「魔方陣の解を求めよ。」
と、問題を出されれば、

1、すべてのパターンを求める
2、対称なパターンがないかチェックする
3、対称性のあったパターンは余分なものなので解ではない（ここでは、3×3のものなら解は一つ）

とするんですが、「魔方陣のすべてのパターンを表示する」だと

1、解を初期値として与える。
2、全パターン表示する

とすると思います。
解を求めるなんて無駄な資源を使いますし。


＞それ以上存在しないことを、何らかの方法で示す必要が生じます。
これは間違いないですね。
考えてみれば明らかに8通りある、ということは必要なようです。
最初のプログラムで8つのパターンが見つかったのが正解である、というものが読み取れますね。

僕の8パターンの表示の仕方は
「3×3行列として表せる魔法陣の一つの解において、対称性があるパターンを表示する」
っていう、ちょっと外れた感じの回答だったみたいです。

ちなみに僕は対称性があるパターンを抜かしたものが魔方陣の解だと思ってるので、そういう風なニュアンスで書いているので悪しからず。

[gtdf]

sizumaさん

＞わざわざ自分が見て理解し難い再帰を使う必要はないと思います。
別に効率がよくなるわけではないし。

はい、自分もそう思いましたが、苦手な再帰も自分の作ったプログラムを改造したものなら
まだ理解できるかもしれないし、どれぐらいすっきりできるのかを知りたかったので・・・

図々しいのですが、自分のプログラムを再帰を使った場合のプログラムを載せてほしいです。

[たいちう]

sizuma さん

> ＞それ以上存在しないことを、何らかの方法で示す必要が生じます。
> これは間違いないですね。

これに同意していただけるならば、違う意見を持っているわけではないと思います。


それとプログラムの訂正。
iとの比較を忘れていました。cよりもeよりも小さいaが、
iより大きいはずはないので、影響は無かったのですが。

if (a > c || a > e || a > i || c > e) continue;


この部分はもちろん、対称パターンの除去を意図しています。
今回の3*3や4*4では手を抜いて最終段階でしていますが、
5*5の計算をする場合はこれを最初にする必要があるでしょう。

a...b
.....
.....
.....
c...d

という配置とした場合、次のような書き方なら
資源の節約という意味において、納得していただけるのではないでしょうか。

for (a = 1; a <= 25; a++)
for (b = 1; b <= 25; b++) {
if (a == b || a > b) continue;
for (c = 1; c <= 25; c++) {
if (a == c || b == c || a > c || b > c) continue;
for (d = 1; d <= 25; d++) {
if (a == d || b == d || c == d || a > d) continue;
...


gtdf さん

> 自分のプログラムを再帰を使った場合のプログラムを載せてほしいです。

何を載せてほしいのか分かりかねますが、
再帰を使って順列を作成した上で魔方陣を求めるプログラムならば作れます。
但し、今日はもう寝るので、日曜か月曜に。それまでに誰かが作っていなかったら。

[sizuma]

再帰を使うなら、使うなりのアルゴリズムで書かなくてはダメです。
再帰で見やすくなるのは、基本的にはデータ構造が再帰的にアクセスするのに適してるものですので。


例えばリスト構造でデータを管理していて、見つかるまでその関数を呼び続ける、とか。
リスト構造とは
A→B→C→D・・・のようなデータ同士がつながっている構造です。


他にも、ソートでも使われるバイナリツリーなどは、再帰を使わないと非常に面倒な処理になります。


無理やり再帰を使うことは出来ますが、演習以外では無駄な処理になります。
よく例で出される階乗を求めるプログラムなんて非常に無駄なものですしね。



ですから、再帰で書く必要はないかな、と思ったわけです。


フリオさんの書かれたプログラムみたいに、再帰を使うためにそれに見合ったアルゴリズムを考える必要があります。

void Magic_Sqr(int a[/url], int n, int m)
{
    int i;
    if(m + 1 == n){
        if(Is_Magic_Sqr(a)) Print(a);
        return;
    }
    for(i = m; i < n; ++ i){
        Swap(a[m], a);
        Magic_Sqr(a, n, m + 1);
        Swap(a[m], a);
    }
}

でも、直感的に分かりやすい表現をする必要があります。
（ブラックボックス的に効率だけを求める、ってのが必要な場合もあるとは思います）
ムリに使うと明らかに不自然に感じますね。
（別にフリオさんのプログラムを見て行ってるわけではありません。・・・ここしか見てないし＾＾；）
こういう再帰の表現も慣れがあるので、しっかりトレース出来るような人ならば、見やすいという人もいるかもしれませんしね。


たいちうさんも書かれてますが、再帰を使うなら最初の
ループで配列を作って、同じ数字があったら違う配列をつくる
という処理を
再帰的に順列を作る
ということなら見やすく出来そうです。（作ったことないですが無駄なループは省くことが出来ると思うので）

[gtdf]

たいちうさん
＞> 自分のプログラムを再帰を使った場合のプログラムを載せてほしいです。

＞何を載せてほしいのか分かりかねますが、
＞再帰を使って順列を作成した上で魔方陣を求めるプログラムならば作れます。

すみません。質問のプログラムの下の部分で、同じような処理を繰り返しているので、
再帰を使えばすっきりとできるのかなと思ったんですが、再帰を使って書くには、やはりフリオさんの
プログラムのMagic_Sqr関数みたいなものを作らないといけないのでしょうか。

自分のプログラムは総当たりですが、この総当たりを再帰を使ってやるにはどうすればよいのかを
知りたいです。（各辺の和が１５といった性質を知らないものとして）

for (i=1; i<=9; i++) {
  data[0] = i;
  for (j=1; j<=9; j++) {
   data[1] = j;
   for (k=1; k<=9; k++) {
    data[2] = k;
    for (l=1; l<=9; l++) {
     data[3] = l;
     for (m=1; m<=9; m++) {
      data[4] = m;
      for (n=1; n<=9; n++) {
       data[5] = n;
       for (o=1; o<=9; o++) {
        data[6] = o;
        for (p=1; p<=9; p++) {
         data[7] = p;
         for (q=1; q<=9; q++) {
          data[8] = q;

[non]

総当たりの再帰

#include <stdio.h>
#define N 4   //9に変更してね
int data[N];
void disp(void)
{
    int i;
    for(i=0;i<N;i++)
        printf("%d ",data);
    printf("\n");
}
void func(int n)
{
    int i;
    if(n==N){
        disp();
        return;
    }
    for(i=1;i<=N;i++){
        data[n]=i;
        func(n+1);
    }
}
int main(void)
{
    func(0);
    return 0;
}

[gtdf]

nonさん

ありがとうございます。おかげで、自分のプログラムをすっきりとすることができました。
(goto文を使ったので、多少見づらくなっていますが)
以下のように改良したのですが、変なところがあれば指摘してください。
総当たりで魔方陣の解を見つけるプログラムです。

#include <stdio.h>

#define N 9   

int data[N];

void disp(void)
{
    int x;
    
    if ((data[0] + data[1] + data[2]) ==
            (data[3] + data[4] + data[5]) &&
            (data[0] + data[1] + data[2]) ==
            (data[6] + data[7] + data[8]) &&
            (data[0] + data[1] + data[2]) ==
            (data[0] + data[3] + data[6]) &&
            (data[0] + data[1] + data[2]) ==
            (data[1] + data[4] + data[7]) &&
            (data[0] + data[1] + data[2]) ==
            (data[2] + data[5] + data[8]) &&
            (data[0] + data[1] + data[2]) ==
            (data[0] + data[4] + data[8]) &&
            (data[0] + data[1] + data[2]) ==
            (data[2] + data[4] + data[6])) 
    {
            for (x=0; x<9; x++) {
                printf("%2d", data[x]);
                if (x % 3 == 2)
                    puts("");    
            }
            puts("");
    }
}
void func(int n)
{
    int c = 0;
    int i, j;
    if(n==N){
        disp();
        return;
    }
    for(i=1;i<=N;i++){
        Label:  if (c > 0) {
            c = 0;
            continue;
                }
                data[n]=i;
                for (j=0; j<n; j++) {
                 if (data[j] == data[n]) {
                c++;
                goto Label;
            }    
                }
                func(n+1);
    }
}
int main(void)
{
    func(0);
    return 0;
}

[non]

悪くはないけど、gotoを使うのはわかりにくいですね。関数にしましょう。

int check(int n)
{
    int j;
    for (j=0; j<n; j++) 
        if (data[j] == data[n]) 
            return 1;
    return 0;
}
                
void func(int n)
{
    int i, j;
    if(n==N){
        disp();
        return;
    }
    for(i=1;i<=N;i++){
        data[n]=i;
        if(!check(n))
            func(n+1);
    }
}

[gtdf]

なるほど。確かに、関数を使えばわかりやすいですね。
やはり、goto文は使うものではありませんね。

ありがとうございます。

[たいちう]

> やはり、goto文は使うものではありませんね。

使い方によります。
濫用するとプログラムが読みにくくなるのは、goto文に限った話ではないですが、
goto文の場合は上手に使うことが難しいので嫌われています。
周囲がgoto文を毛嫌いしている中では、うまい使い方を目にする機会が少ないことと、
下手に使って叩かれることを恐れ萎縮したりするので、上手に使うことが更に難しくなるわけです。

No:45874は、gotoを使うべき状況ではないですね。


それと細かいことですが、次のように書いた方が可読性が増します。
ミスが減ることも期待できます。

int sum = data[0] + data[1] + data[2];
if (data[3] + data[4] + data[5] == sum &&
    data[6] + data[7] + data[8] == sum &&
    data[0] + data[3] + data[6] == sum &&
    data[1] + data[4] + data[7] == sum &&
    data[2] + data[5] + data[8] == sum &&
    data[0] + data[4] + data[8] == sum &&
    data[2] + data[4] + data[6] == sum) 
{

[gtdf]

実は、初めてgoto文を使ったんです。
Wikipediaによると、プログラムの構造を熟知したプログラマが状況に応じて使い分けるものとされている。
だそうですね。

＞それと細かいことですが、次のように書いた方が可読性が増します。
ミスが減ることも期待できます。

確かにそうですね。もっと見やすいプログラムがかけるよう練習します。

[たいちう]

いらないかもしれないけど再帰で順列の魔方陣を作りました。
フリオさんのものと似ていますが、もっと素朴で判りやすいと思います。
順列の生成方法を理解するためには、(A)のコメントアウトを復活させて、
(B)をコメントアウトしてデバッガで追ってみると良いと思います。
その際、Nは3か4程度が良いでしょう。

#include <stdio.h>

#define N 9

int num[N];

void check() {
    static int c;
    int i, j, sum = 0, temp;

    // 横
    for (j = 0; j < 3; j++) {
        temp = 0;
        for (i = 0; i < 3; i++)
            temp += num[i + j * 3];
        if (sum == 0)
            sum = temp;
        else if (temp != sum) return;
    }

    // 縦
    for (i = 0; i < 3; i++) {
        temp = 0;
        for (j = 0; j < 3; j++)
            temp += num[i + j * 3];
        if (temp != sum) return;
    }

    // 斜め
    if (num[0] + num[4] + num[8] != sum) return;
    if (num[2] + num[4] + num[6] != sum) return;

    // 対称解の除去
    if (num[0] > num[2] || num[0] > num[6] || num[0] > num[8] || num[2] > num[6]) return;

    // 解の表示
    printf("%d:\n", ++c);
    for (i = 0; i < N; i++)
        printf("%s%d%c", i % 3 == 0 ? "    " : "", num, i % 3 == 2 ? '\n' : ' ');
    printf("\n");
}

void swap(int i, int j) {
    int temp;
    if (i == j) return;

    temp = num;
    num = num[j];
    num[j] = temp;
}

void permutation(int n) {
    int i;
    if (n == N) {
/* (A)
        for (i = 0; i < N; i++)
            printf("%d ", num);
        printf("\n");
*/

        check(); // (B)

        return;
    }
    for (i = n; i < N; i++) {
        swap(i, n);
        permutation(n + 1);
        swap(i, n);
    }
}

int main() {
    int i;
    for (i = 0; i < N; i++)
        num = i + 1;

    permutation(0);

    // quit
    printf("End.\n");
    getchar();
    return 0;
}

[gtdf]

たいちうさん

ありがとうございます。再帰の部分も、紙に書き出していったらなんとか理解できました。
確かに順列が生成されていました。

一つ質問があるのですが、対称解の除去が

if (num[0] > num[2] || num[0] > num[6] || num[0] > num[8] || num[2] > num[6])
　return;

と表せるのはなぜでしょうか。

[たいちう]

まず対称解除去の部分をコメントアウトして、全ての解を表示してください。
次に条件を次のように変えて実行して下さい。

if (num[0] > num[2] || num[0] > num[6] || num[0] > num[8])
　return;

解はそれぞれ8つと2つ表示されるはずです。
後者は左上を4隅の最小にすることで、回転対称を除去しています。

もう一つの条件については、もう一度考えてみてください。

[gtdf]

わかりました。

最後の条件は、転置行列の除去ですよね？

[たいちう]

正解です。

[gtdf]

みなさん、こんなにも回答していただきありがとうございました。
色々なやり方があることを知れて、非常に勉強になりました。

また、質問したときもよろしくお願いします。