ナンバープレイスについての考察(3)を紹介します。
考察(3)
9×9の盤のマス目に数字1から9を書き込む。ただし、次の条件を満たすこと。
(条件1)縦の列、横の行に1から9までの数字がひとつずつ入る。
(条件2)3×3の正方形ブロック内に1から9までの数字がひとつずつ入る。
上の条件を満たす配置をすべて求めるプログラムを作成せよ。
マス目dから行iは、(d-1)/9+1 で、列jは、(d-1)%9+1 で、
ブロックkは、((i-1)/3)*3+(j-1)/3+1 で求められる。
●プログラム(np311.c)
/* << np311.c >> */ /* 9×9のナンバープレース */ #include <stdio.h> int a[10][10], /* マス目を表す配列。*/ gyo[10][10], /* gyo[i][m]=0は、i行に数字mが出現していない。 gyo[i][m]=1は、i行に数字mが出現している。*/ retu[10][10], /* retu[i][m]=0は、i列に数字mが出現していない。 retu[i][m]=1は、i列に数字mが出現している。*/ block[10][10],/* 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<=9; i++ ) { for( j=1; j<=9; j++ ) { scanf("%d",&a[i][j]); } } /* 初期設定。*/ for( i=1; i<=9; i++ ) { for( j=1; j<=9; j++ ) { gyo[i][j] = 0; retu[i][j] = 0; block[i][j] = 0; } } for( i=1; i<=9; i++ ) { for( j=1; j<=9; j++ ) { m = a[i][j]; if( m > 0 ) { gyo[i][m] = 1; retu[j][m] = 1; k = ((i-1)/3)*3 + (j-1)/3 + 1; block[k][m] = 1; } } } count = 0; /* バックトラック。*/ gen(1); /* 配置の個数の表示。*/ printf("9×9 配置の個数:%d\n",count); } /* マス目dに数字mを割り当てる再帰的手続き。*/ void gen(int d) { int i,j,k,m; if( d > 81 ) { /* 配置の表示。*/ count++; printf("[%d]\n",count); for( i=1; i<=9; i++ ) { for( j=1; j<=9; j++ ) { printf("%3d",a[i][j]); } printf("\n"); } return; } /* マス目dに対応する行i、列jを求める。*/ i = (d-1)/9 + 1; j = (d-1)%9 + 1; /* マス目が空(a[i][j]=0)の場合、割り当てる数字を求める。 空でない場合、つぎのマス目に進む。*/ if( a[i][j] == 0 ) { /* マス目dに対応するブロックkを求める。*/ k = ((i-1)/3)*3 + (j-1)/3 + 1; /* すべての数字m(1≦m≦9)について、マス目に割り当ててよいか どうかチェックする。*/ for( m=1; m<=9; m++ ) { if( (gyo[i][m] == 0)&&(retu[j][m] == 0)&& (block[k][m] == 0) ) { /* 割り当て可能なので、マス目dに数字mを設定。*/ 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); } }