第27講 数独（ナンプレ）自動生成
第１話 数独（ナンプレ）とは？

数独（ナンプレ）の問題を例示してみましょう。

そして、これの答は

答から、ルールは推測できるのではないでしょうか。
各セルは、４つの条件を満たさなければなりません。
①　１から９までの数字が入る。
②　列の数字が重複してはならない。　
③　行の数字が重複してはならない。
④　ブロックの数字が重複してはならない。
そうです。前講の最後に

第24講 特殊種法で魔方陣を超高速に自動生成する
を受けて、数独自動生成に取り組むことにします。

と書いたように、特殊種とルールが大変似ています。

①　１から９までの数字が入る。
②　列の数字が重複してはならない。　
③　行の数字が重複してはならない。
までは同じで、違いは
④　ブロックの数字が重複してはならない。
がないことと対角線と逆対角線の条件が特殊種にはあることです。


つまり、第24講第５話で作った
#include<iostream>
using namespace std;
int f(int g,int m[10][10],int n,int* p,int* q,int cn);
void h(int m[10][10],int n);
void zh(int n,int *p,int *q);
void sy(int m[10][10],int n);
void main(){
　　 int m[10][10],n,t=0;
　　 while(1){
　　　　　cout<<"何次魔方陣種を自動生成しますか。"<<endl;
　　　　　t=1;
　　　　　if(n!=6)break; else cout<<"6以外の数字を入れて下さい。"<<endl;
　　 }
　　 if(t==1)scanf("%d",&n);
　　 sy(m,n);
　　 int p[100],q[100];
　　 zh(n,p,q);
　　 cout<<n<<"次魔方陣種が"<<endl<<f(0,m,n,p,q,0)<<"個できました。"<<endl;;
　　 cout<<"プロジェクト終了"<<endl;
}
void zh(int n,int *p,int *q){
　　 int i,j,cn;
　　 int a[10][10];
　　 for(i=0;i<n;i++)
　　　　　for(j=0;j<n;j++)
　　　　　　　 a[i][j]=-1;
　　 for(i=0;i<n;i++)a[i][i]=i;
　　 cn=n;
　　 for(i=0;i<n;i++){
　　　　　if(a[i][n-1-i]==-1){
　　　　　　　 a[i][n-1-i]=cn;
　　　　　　　 cn++;
　　　　　}
　　 }
　　 for(i=0;i<n;i++){
　　　　　for(j=0;j<n;j++){
　　　　　　　　 if(a[i][j]==-1){
　　 　　　　　　　　a[i][j]=cn;
　　　　　　　　　　 cn++;
　　　　　　　　 }
　　　　　}
　　 }
　　 for(i=0;i<n;i++){
　　　　　for(j=0;j<n;j++){
　　　　　　　 p[a[i][j]]=j;
　　　　　　　 q[a[i][j]]=i;
　　　　　}
　　 }
}
int f(int g,int m[10][10],int n,int* p,int* q,int cn){
　　 int i,j,x,y;
　　 x=p[g];
　　 y=q[g];
　　 for(i=1;i<=n;i++){
　　　　　m[y][x]=i;
　　　　　if(g>0){
　　　　　　　 if(g<n){
　　　　　　　　　　for(j=0;j<g;j++){
　　　　　　　　　　　　 if(m[j][j]==m[y][x])goto tobi;
　　　　　　　　　　}
　　　　　　　 }
　　　　　}
　　　　　if(x==n-1-y && x!=y){
　　　　　　　 for(j=0;j<y;j++){
　　　　　　　　　　if(m[j][n-1-j]==m[y][x])goto tobi;
　　　　　　　 }
　　　　　　　 if(m[x][x]==m[y][x])goto tobi;
　　　　　　　 if(m[y][y]==m[y][x])goto tobi;
　　　　　}
　　　　　if(x!=y && x!=n-1-y){
　　　　　　　 for(j=0;j<x;j++){
　　　　　　　　　　if(m[y][j]==m[y][x])goto tobi;
　　　　　　　 }
　　　　　　　 for(j=0;j<y;j++){
　　　　　　　　　　if(m[j][x]==m[y][x])goto tobi;
　　　　　　　 }
　　　　　　　 if(m[y][y]==m[y][x])goto tobi;
　　　　　　　 if(m[x][x]==m[y][x])goto tobi;
　　　　　　　 if(m[y][n-1-y]==m[y][x])goto tobi;
　　　　　　　 if(m[n-1-x][x]==m[y][x])goto tobi;
　　　　　}
　　　　　if(g+1<n*n){
　　　　　　　 cn=f(g+1,m,n,p,q,cn);
　　　　　　　 //if(cn==100)return(cn);
　　　　　}
　　　　　else{
　　　　　　　 h(m,n);
　　　　　　　 cout<<endl<<endl;
　　　　　　　 //if(cn==100)return(cn);
　　　　　　　 cn++;
　　　　　}
　　　　　tobi:;
　　 }
　　 return(cn);
}
void h(int m[10][10],int n){
　　 int i,j;
　　 for(i=0;i<n;i++){
　　　　　for(j=0;j<n;j++){
　　　　　　　 //if(m[i][j]<10)cout<<"0"<<m[i][j]<<" ";
　　　　　　　 cout<<m[i][j]<<" ";
　　　　　}
　　　　　cout<<endl;
　　 }
}
参考ダウンロード添付ファイル
を改良すれば、数独自動生成は出来ます。
対角線と逆対角線の条件は後で考えることにして、
とりあえず、
　　 int m[10][10],n,t=0;
　　 while(1){
　　　　　cout<<"何次魔方陣種を自動生成しますか。"<<endl;
　　　　　t=1;
　　　　　if(n!=6)break; else cout<<"6以外の数字を入れて下さい。"<<endl;
　　 }
　　 if(t==1)scanf("%d",&n);
は
　　 int m[10][10],n=9;
に変更して下さい。
ただし、

となってしまいますので、

＊を使い境界線を引きましょう。
上はブロックの条件はまだ加えていませんので、
ブロック内の重複はまだあります。
これは後で解消します。
また、答は無数近くありますから１００個生産できた段階で止めるようにしましょう。

eclipse c++ 入門講義第１部へ

eclipse c++ 入門講義第２部へ