ナンバープレイスについての考察（２）

ナンバープレイスについての考察（２）を紹介します。

考察（２）

　4×4の盤のマス目に数字1から4を書き込む。ただし、次の条件を満たすこと。

　　（条件１）縦の列、横の行に1から4までの数字がひとつずつ入る。
　　（条件２）2×2の正方形ブロック内に1から4までの数字がひとつずつ入る。

　上の条件を満たす配置をすべて求めるプログラムを作成せよ。

●プログラム(np211.c)

/* << np211.c >> */
/* 4×4のナンバープレース */

#include <stdio.h>
int a[5][5],    /* 4×4のマス目を表す配列。*/  
    gyo[5][5],  /* gyo[i][m]=0は、i行に数字mが出現していない。   
                   gyo[i][m]=1は、i行に数字mが出現している。*/   
    retu[5][5], /* retu[i][m]=0は、i列に数字mが出現していない。   
                   retu[i][m]=1は、i列に数字mが出現している。*/   
    block[5][5],/* block[i][m]=0は、iブロックに数字mが出現していない。 
                  block[i][m]=1は、iブロックに数字mが出現している。*/ 
    count;      /* 配置の個数。*/                                
void gen(int d);

int main() {
  int i,j,k,m;

  /* 問題の読み込み。*/                                        
  for( i=1; i<=4; i++ ) {                                      
    for( j=1; j<=4; j++ ) { scanf("%d",&a[i][j]); }            
  }                                                            

  /* 初期設定。*/                                              
  for( i=1; i<=4; i++ ) {                                      
    for( j=1; j<=4; j++ ) {                                    
      gyo[i][j] = 0;  retu[i][j] = 0; block[i][j] = 0;         
    }                                                          
  }                                                            
  for( i=1; i<=4; i++ ) {
    for( j=1; j<=4; j++ ) {
      m = a[i][j];
      if( m > 0 ) {
        gyo[i][m] = 1; retu[j][m] = 1;
        k = ((i-1)/2)*2 + (j-1)/2 + 1;
        block[k][m] = 1;
      }
    }
  }
  count = 0;

  /* バックトラック。*/
  gen(1);

  /* 配置の個数の表示。*/
  printf("4×4 配置の個数：%d\n",count);
}

/* マス目dに数字mを割り当てる再帰的手続き。*/
void gen(int d) { 
  int i,j,k,m;

  if( d > 16 ) {
    /* 配置の表示。*/
    count++; printf("[%d]\n",count);
    for( i=1; i<=4; i++ ) {
      for( j=1; j<=4; j++ ) { printf("%3d",a[i][j]); }
      printf("\n");
    }
    return;
  }

  /* マス目dに対応する行i、列jを求める。*/
  i = (d-1)/4 + 1; 
  j = (d-1)%4 + 1;  

  /* マス目が空(a[i][j]=0)の場合、割り当てる数字を求める。
　 　　　　　空でない場合、つぎのマス目に進む。*/
  if( a[i][j] == 0 ) {
    /* マス目dに対応するブロックkを求める。*/
    k = ((i-1)/2)*2 + (j-1)/2 + 1;  

    /* すべての数字m(1≦m≦4)について、マス目に割り当ててよいか
       どうかチェックする。*/
    for( m=1; m<=4; m++ ) {                           
      if( (gyo[i][m] == 0)&&(retu[j][m] == 0)&&         
          (block[k][m] == 0) ) {                   
        /* 割り当て可能なので、マス目に数字を設定。*/
        a[i][j] = m; 
        gyo[i][m] = 1; 
        retu[j][m] = 1; 
        block[k][m] = 1;

        /* つぎのマス目d+1に進む。*/
        gen(d+1);

        /* 割り当て解除。*/
        a[i][j] = 0;
        gyo[i][m] = 0;
        retu[j][m] = 0;
        block[k][m] = 0; 
      }
    }                                              
  } else {
    /* つぎのマス目d+1に進む。*/
    gen(d+1);
  }                                                
}