c言語において２部グラフマッチングプログラムを用いてラテン方陣を書きたいです。当方初心者です。

Question

C言語で2部グラフのマッチングを求めるプログラムを利用してラテン方陣を書きたいのですが、マッチングする行をfor文で回せばいいということがわかるのですが、マッチングしたものを保存して、再度マッチングさせるのがどうすれば上手く行くのかわかりませんでした。プログラムは６×６行列です。またマッチングしたものを最後行列として表示する方法についても悩んでいます。
下記は１つの２部グラフマッチングを求めるプログラムです。
一番下は元のプログラムで、教えてもらったもので
０１２３ ４ ５
６７８９１０１１の点でのマッチングを表しています。

ですが配列内の動きを見たかったと、少しマッチングしたものが見にくかったので表示を
１２３４５６
１２３４５６の点として表示を考えたのが上のプログラムです。

方法としては
２部グラフでのマッチングを求めるプログラムですので、マッチングした下の点を保存して、上の点として扱い再度マッチングすべきもとの点を探す様にしたいです。

さらに要領としては回目は1＝｛2，3，4，5，6｝の点とマッチングが可能で２を選んだ場合２回めでは2＝｛3，4，5，6｝の点から選べるという様に１回ずつ各点が選べる回数が減っていけば最終的に決定すると考えられます。なので、はじめは上の一つの点から自身を除いた全ての点にパスが出ている状態から、回数を重ねるごとにパスが減っていく様にすれば自然とラテン方陣としてできると考えられます。

例えば
１２３４５で作った場合で、２行目で
５４２３１となった場合

５４２３１の結果を元にマッチングを行い
３１４５２とマッチングさせる
という様にすれば
求めたい行の回数分行う事によってラテン方陣ができると思います。
最終的には

１２３４５
５４２３１
３１４５２
４５１２３
２３５１４

というような形に表示をしたいです。

教えてくださる方がいたらよろしくお願いします。

コード
#include <stdio.h>
#include <stdlib.h>
#define V 12
#define L_IDX 6

int A[V][V];
int MV[V];
int P[V];
int aug(int, int *);

int main(){
  int  i, j, p, q, r;
  int find;
  r=V/2;
   

  for(i=0;i<V;i++){
    for(j=0;j<V;j++){
      A[i][j] = 0;
    }
  }
  /*
  A[0][6] = 1, A[0][7] = 1;
  A[1][6] = 1, A[1][7] = 1;
  A[2][6] = 1, A[2][7] = 1;
  A[3][5] = 1, A[3][6] = 1;
  A[4][5] = 1, A[4][7] = 1, A[4][8] = 1, A[4][9] = 1;
  */
  A[0][6] = 1, A[0][7] = 1;
  A[1][6] = 1, A[1][7] = 1, A[1][9] = 1;
  A[2][6] = 1, A[2][7] = 1, A[2][8] = 1;
  A[3][8] = 1, A[3][9] = 1, A[3][10] = 1;
  A[4][8] = 1, A[4][9] = 1, A[4][11] = 1;
  A[5][10] = 1, A[5][11] = 1;

  for(i=0;i<V;i++){MV[i] = 0;}

  find = 1;
  while(find){
    find = 0;
    for(i=0;i<V;i++){P[i] = 0;}

    for(i=0;i<L_IDX;i++){
      if(MV[i]==0){
	P[i] = 1;
	find = aug(i,P);
   
   if(find){
	  //***********************************************************

    for(p=0;p<V;p++){
      for(q=0;q<V;q++){
         if(q%r==0)printf("|");
　　　　    printf("%2d",A[q][p]);
	     }
	    printf("\n");
	   }
	    printf("+++++++++++++++++++++++++++\n");
            printf("\n");
	  //***********************************************************
	  MV[i] = 1;
	  break;
	}
	P[i] = 0;
      }
    }
  }

  for(i=r;i<V;i++){
    for(j=0;j<r;j++){
      if(A[i][j]==1){ printf("A[%d][%d]=%d ",i%6+1,j,A[i][j]);} //マッチングしてる箇所を表示
    }
  }
  printf("\n");

   for(i=r;i<V;i++){
     for(j=0;j<r;j++){
      if(A[i][j]==1){ printf("%3d",j);//マッチング後を表示  
    }  
   }
  }
}

int aug(int v, int P[]){
  int i,j,k;
  int find,v1,v2;
   
  for(j=0;j<V;j++){
    
    if(A[v][j]==1&&P[j]==0){
      P[j] = 1;
      find = aug(j,P);
      if(find==1){ //found augmenting path
	A[v][j] = 0, A[j][v] = 1, MV[j] = 1; 
	return(1);
      }
      P[j] = 0;
    }
      
  }// end for j
  
  if(v>=L_IDX&&MV[v]==0){
    return(1); // found augmenting path
  }else{
    return(0); // could not find augmenting path
  } 
}

元のプログラム

コード
#include <stdio.h>
#include <stdlib.h>
#define V 12
#define L_IDX 6
int A[V][V];
int MV[V];
int P[V];
int aug(int, int *);

int main(){
  int  i, j, p, q;
  int find;
  
  for(i=0;i<V;i++){
    for(j=0;j<V;j++){
      A[i][j] = 0;
    }
  }
  /*
  A[0][6] = 1, A[0][7] = 1;
  A[1][6] = 1, A[1][7] = 1;
  A[2][6] = 1, A[2][7] = 1;
  A[3][5] = 1, A[3][6] = 1;
  A[4][5] = 1, A[4][7] = 1, A[4][8] = 1, A[4][9] = 1;
  */
  A[0][6] = 1, A[0][7] = 1;
  A[1][6] = 1, A[1][7] = 1, A[1][9] = 1;
  A[2][6] = 1, A[2][7] = 1, A[2][8] = 1;
  A[3][8] = 1, A[3][9] = 1, A[3][10] = 1;
  A[4][8] = 1, A[4][9] = 1, A[4][11] = 1;
  A[5][10] = 1, A[5][11] = 1;

  for(i=0;i<V;i++){MV[i] = 0;}

  find = 1;
  while(find){
    find = 0;
    for(i=0;i<V;i++){P[i] = 0;}
    
    for(i=0;i<L_IDX;i++){
      if(MV[i]==0){
	P[i] = 1;
	find = aug(i,P);
	if(find){
	  //***********************************************************	  
	  for(p=L_IDX;p<V;p++){
	    for(q=0;q<L_IDX;q++){
	      printf("%d ",A[p][q]);
	    }
	    printf("\n");
	  }
	  printf("++++++++++++++++++++++++++\n");
	  //***********************************************************	  
	  MV[i] = 1;
	  break;
	}
	P[i] = 0;
      }
    }
  }

  for(i=L_IDX;i<V;i++){
    for(j=0;j<L_IDX;j++){
      if(A[i][j]==1){ printf("A[%d][%d]=%d ",i,j,A[i][j]);}
    }
  }
  printf("\n");

}

int aug(int v, int P[]){
  int i,j,k;
  int find,v1,v2;
   
  for(j=0;j<V;j++){
    
    if(A[v][j]==1&&P[j]==0){
      P[j] = 1;
      find = aug(j,P);
      if(find==1){ //found augmenting path
	A[v][j] = 0, A[j][v] = 1, MV[j] = 1; 
	return(1);
      }
      P[j] = 0;
    }
      
  }// end for j
  
  if(v>=L_IDX&&MV[v]==0){
    return(1); // found augmenting path
  }else{
    return(0); // could not find augmenting path
  }
  
}
 

Comments

[Orlofsky]

コードは https://teratail.com/help#about-markdown の [コードを入力] に修正してください。そうしないと誰も読まないでしょう。

[naberyo]

修正いたしました
ご指摘ありがとうございます。

[Orlofsky]

字下げが雑過ぎ。
コードを読んでもらいたかったら、意味のある字下げに直しましょう。

[naberyo]

申し訳ありません
ご指摘の通りです

[rubato6809]

このプログラムは質問者が作成したものですか？或いはどこからかコピーしたとか？
このプログラムが配列A[12][12]を６回表示、最後に2行表示していることはわかりました。
「マッチングしたものを保存して」…このプログラム中に保存したい状態がありますか？
「再度マッチングさせる」…とは、どんなイメージなんでしょうか、できるだけ具体的に。
「マッチングしたものを最後行列として表示する方法」…このプログラムを改造して表示できるとしたら、どんな表示結果を望みますか？できるだけ具体的に示してください。
私を含め回答者は、C言語は使えても、こうした問題自体や、質問者の望むことがよくわからない、つまり何をアドバイスできるかわからない人が多いと思いました。

Answer 1

ラテン方陣というと数独なので、過去に数独を解くプログラムを書いたときの方法を書きます

・すべてのマスに入りうる候補を割り当てていく
(縦横を見て、1,2,3が使われていれば、そのマスには4,5,6のいずれかが入る)
・もし候補が1個だけなら確定する
・各列や行の候補の数をカウントしていく
もし1つだけの候補があれば、確定する
(ある列を見たとき、1が入りうるマスは1個なら、そこが確定する)
・確定した場合、その列と行から候補を消す
(1とわかったら、同じ列と行の他のマスの候補から1を消す)

・すべてのマスを調べて候補が1つか
・列、行の合計をだして候補が1つか
この2つを確定するマスが出なくなるまで繰り返します

ただ、数独では答えが一意になるのにこのアルゴリズムでは全部のマスが確定しないことがあります
ラテン方陣のルールだとこれが発生するかどうかはわかりません

なんの候補が残っているか、はビットで管理していました
ググれば、候補が1つだけ＝1ビットだけ立ってる＝(2^nの数)というのを
分岐無しで求める方法も使えます