第27講 数独（ナンプレ）自動生成
第７話 数独解答自動生成ソフト完成

を実現するプログラム例
#include<iostream>
#include<ctime>
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(){
　　 clock_t hj,ow; //clock_t型の宣言、プログラム開始時間を取得するための変数
　　 hj=clock();
　　 int m[10][10],n=9;
　　 sy(m,n);
　　 int p[100],q[100];
　　 zh(n,p,q);
　　 cout<<"数独が"<<f(0,m,n,p,q,0)<<"個できました。"<<endl;
　　 ow=clock();
　　 cout<<"生成にかかった時間は"<<(double)(ow-hj)/1000<<"秒です。"<<endl;
　　 cout<<"プロジェクト終了"<<endl;
}
void sy(int m[10][10],int n){
　　 int i,j;
　　 for(i=0;i<n;i++)
　　　　　for(j=0;j<n;j++)
　　　　　　　 m[i][j]=0;
}
void zh(int n,int *p,int *q){
　　 int i;
　　 for(i=0;i<n*n;i++)p[i]=i%n;
　　 for(i=0;i<n*n;i++)q[i]=i/n;
}
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(x>0)for(j=0;j<x;j++)if(m[y][x]==m[y][j])goto tobi;
　　　　　if(y>0)for(j=0;j<y;j++)if(m[y][x]==m[j][x])goto tobi;
　　　　　for(j=y-y%3;j<y-y%3+3;j++){
　　　　　　　 for(k=x-x%3;k<x-x%3+3;k++){
　　　　　　　　　　if(9*j+k==g)goto tobi1;
　　　　　　　　　　if(m[y][x]==m[j][k])goto tobi;
　　　　　　　 }
　　　　　}
　　　　　tobi1:;
　　　　　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+1;i++){
　　　　　if(i%3==0){
　　　　　　　 for(j=0;j<n+4;j++)cout<<" *";
　　　　　　　 cout<<endl;
　　　　　　　 if(i==n)break;
　　　　　}
　　　　　for(j=0;j<n+1;j++){
　　　　　　　 //if(m[i][j]<10)cout<<"0"<<m[i][j]<<" ";
　　　　　　　 if(j==0)cout<<" * ";
　　　　　　　 if(j>0 && j%3==0)cout<<"* ";
　　　　　　　 if(j<n)cout<<m[i][j]<<" ";
　　　　　}
　　　　　cout<<endl;
　　 }
}
参考ダウンロード添付ファイル

解説
以下の説明は、現在

２２のセルにいるという前提でお読み下さい。
q[22]すなわち2から0をいかに作り出すか、
p[22]すなわち4から3をいかに作り出すか、
の解答は、
2-2%3=2-2=0
4-4%3=4-1=3
です。
そして、jとkから白い番号を

を作り出す方法は、１４を例に取れば、
9×1＋5＝１４
です。
break; のタイミングは
jとkから作り出した数字が２２と等しくなる時点です。
つまり、１４＜２２が成立している間は、
重複検査を続けなければなりません。
jとkの動きによって、
３→４→５→１２→１３→１４→２１→２２
と動きますよね。
ですから比較対象は２２未満ということになるのです。
ですから、
jとkから作り出した数字が２２になった時点で強制的にfor文を抜け出せばよいのです。
　　　　　for(j=y-y%3;j<y-y%3+3;j++){
　　　　　　　 for(k=x-x%3;k<x-x%3+3;k++){
　　　　　　　　　　if(9*j+k==g)goto tobi1;
　　　　　　　　　　if(m[y][x]==m[j][k])goto tobi;
　　　　　　　 }
　　　　　}
の
　　　　　　　　　　if(9*j+k==g)goto tobi1;
　　　　　　　　　　if(m[y][x]==m[j][k])goto tobi;
２つの順番を逆にすると、数独は１個も出来ませんね。
うっかり自分自身と比較すれば、
必ず等しくなりgoto tobi;が実行されてしまい、
空振りに終わります。
順番が違うだけで、天国と地獄を味わうことになります。

他の方法も試す予定でしたが、
気力が失せました。
（皆さんは、是非取り組んでみて下さい。）
余りにも難しすぎたからです。

ただ、次のことは試してみたいと思います。
それは、数字を入れる順番は

と

では、どちらの方が速く数独ができるかです。
魔方陣の場合には、
明らかに対角線の方が条件がきついので、
そこから埋めることにより、
かなり高速になりました。
とくに、条件の強いセルのない数独では、
順番の変更は意味がないのでしょうか。
こればかりは、実験してみないと分かりません。
このように数字を入れる順番を変更するには、
再び
void zh(int n,int *p,int *q){
　　 int i;
　　 for(i=0;i<n*n;i++)p[i]=i%n;
　　 for(i=0;i<n*n;i++)q[i]=i/n;
}
の部分をいじらなければなりません。
どう変更したらよいでしょうか。

上は番号付けが上手くいっているかを確認するための出力です。
若干、表示関数がいじってあります。
これを実現して下さい。
ヒントは、
void zh(int n,int *p,int *q){
　　 int i,j,k,l,cn,a[9][9];
　　 for(i=0;i<3;i++){
　　　　　for(j=0;j<3;j++){
　　　　　　　 for(k=0;k<3;k++){
　　　　　　　　　　for(l=0;l<3;l++){
　　　　　　　　　　　　　　・・・・
と４次元for文にすることです。
そして、i,j,k,lをどう組み合わせるかです。
組み合わせによっては、
　　 for(i=0;i<9;i++){
　　　　　for(j=0;j<9;j++){
　　　　　　　　・・・・
と同じになってしまいます。

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

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