数の三角形問題（７）考察２

　数の三角形問題（７）考察２を示します。

（７）考察２

　プログラムによる解の探索を考察する。

　○に記号 x(1),…,x(9)を割り当てる。

　　　　　　　x(1)
　　　　　x(9)　　x(2)
　　　x(8)　　 　　　　 x(3)
　x(7) 　　x(6)　 　x(5)　　 x(4)

　辺の中央の2個の○の値は、交換しても本質的な違いはないので、

　　x(2)＜x(3)、x(5)＜x(6)、x(8)＜x(9)

と仮定する。

　得られた配置で回転して重なるもの、裏返して重なるものは同じと見なすと、
頂点x(1),x(4),x(7)において、x(1)＜x(4)＜x(7)を満たすものを列挙すればよい。

・m=17の場合

　x(1)+x(4)+x(7)=6　となり、つぎの組が該当する。

(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)

　x(1)＜x(4)＜x(7)から、x(1)=1,x(4)=2,x(7)=3 となり、

が見つかる。

　m=18,22には解がないことがプログラムの実行結果からわかる。

/* << sankaku.c >> */                                            
/* 数の三角問題の解を求める。*/                                  
#include <stdio.h>                                               
int x[10], /* 順列を保存する配列。*/                             
    count, /* 順列の個数。*/                                     
    m;     /* mの値。*/                                          
void perm(int k);                                                
                                                                 
int main() {                                                     
  int i;                                                         
                                                                 
  while( 1 ) {                                                   
    /* mの値を読み込む。*/                                       
    scanf("%d",&m);                                              
    if( m <= 0 ) { break; }                                      
                                                                 
    /* 初期設定。*/                                              
    for( i=1; i<=9; i++ ) { x[i] = i; }                          
    count = 0;                                                   
                                                                 
    /* 順列の生成。*/                                            
    perm(1);                                                     
    printf("m=%d  解の個数：%d\n\n",m,count);
  }                                                              
}                                                                
                                                                 
/* 順列を生成する再帰関数を基に、解を探索する。*/                
void perm(int k) {                                               
  int i,s,w;                                                     
                                                                 
  if( k == 5 ) {
    /* 辺{x(1),x(2),x(3),x(4)}の条件を調べ、満たさなければ戻る。*/
    s = x[1]+x[2]+x[3]+x[4];
    if( s != m ) { return; }
    if( x[2] > x[3] ) { return; }
  }

  if( k == 8 ) {
    /* 辺{x(4),x(5),x(6),x(7)}の条件を調べ、満たさなければ戻る。*/
    s = x[4]+x[5]+x[6]+x[7];
    if( s != m ) { return; }
    if( x[5] > x[6] ) { return; }
  }
  
  if( k > 9 ) {
    /* 辺{x(7),x(8),x(9),x(1)}の条件を調べ、満たさなければ戻る。*/
    s = x[7]+x[8]+x[9]+x[1];
    if( s != m ) { return; }
    if( x[8] > x[9] ) { return; }
    
    /* 各グループの代表に絞る。*/
    if( (x[1] < x[4])&&(x[4] < x[7]) ) {
      /* 解の出力。*/
      count++;                                
      printf("[%2d]",count);            
      /* 三角形の頂点をかっこで囲む。*/
      for( i=1; i<=9; i++ ) { 
        if( i%3 == 1 ) { printf("("); }             
        printf("%2d",x[i]); 
        if( i%3 == 1 ) { printf(")"); }       
      }                                       
      printf("\n");                                        
    }
    retuen;
  }
    
  for( i=k; i<=9; i++ ) {                            
    /* 交換。*/
    w = x[k]; x[k] = x[i]; x[i] = w;                 
    perm(k+1); 
    /* 交換を戻す。*/                                
    w = x[k]; x[k] = x[i]; x[i] = w;            
  }                                                    
}