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

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

　ナンバープレイスとは、9×9盤のマス目に数字1から9を書き込むパズルである。ただし、次の条件を満たす。

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

考察（１）

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

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

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

●プログラム（np111.c）

/* << np111.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,m;

  /* 初期設定。*/
  for( i=1; i<=4; i++ ) {
    for( m=1; m<=4; m++ ) {
      gyo[i][m] = 0;  retu[i][m] = 0; block[i][m] = 0;
    }
  }
  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、ブロックkを求める。*/
  i = (d-1)/4 + 1; 
  j = (d-1)%4 + 1;  
  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);

      /* 割り当て解除。*/
      gyo[i][m] = 0;
      retu[j][m] = 0;
      block[k][m] = 0;
    }
  }
}