#include <iostream.h> #include <conio.h> #include <stdio.h> #include <stdlib.h> #include <math.h> void Step1(void); void Step2(void); typedef int TCandidat[9]; TCandidat mesh[9][9]; int start[9][9], roll[9][9]; int board[9][9]; int tempi=0,tempj=0; TCandidat temp_cand; int Rall_number=0; int cont=0; int old_opened=-1; //void Step1(void); //void Step2(void); void Cand_Init(TCandidat a) {int i; for(i=0;i<9;i++) a[i]=1; } void Init_9_9( int a[9][9]) {int i,j; for(i=0;i<9;i++) for(j=0;j<9;j++) a[i][j]=0; } int Cand_Count(TCandidat a) {int i, c=0; for(i=0;i<9;i++) if (a[i]==1) c++; return c; } int Unic_RCM(int a,int b, int val) {int i,j,flag=0; // unic in a row for(j=0;j<9;j++) if(board[a][j]==val) flag++; if (flag==0) //unikalno v stroke, proverjaem stolbets {for(i=0;i<9;i++) if(board[i][b]==val) flag++; } if (flag==0) //unikalno i v stroke, i v stolbtse, proverim sector {for(i=(a/3)*3;i<(a/3)*3+3;i++) for(j=(b/3)*3;j<(b/3)*3+3;j++) if(board[i][j]==val) flag++; } if( flag==0) return 1; // chislo unikalno else return 0; // chislo ne unikalno } int Cand_to_Number(TCandidat a) {int i,c=0; for(i=0;i<9;i++) if(a[i]==1) {c=i+1; break; } return c; } void Step1(void) {for(int i=0;i<9;i++) for(int j=0;j<9;j++) board[i][j]=start[i][j]; // find a place for a value do { tempi=random(9); tempj=random(9); } while(board[tempi][tempj]!=0); // cout<<"\nposition:"<<tempi<<" "<<tempj; //find a value int val_count=0, temp_val; Cand_Init(temp_cand); while(val_count<9) {do {temp_val=random(9); } while(temp_cand[temp_val]==0);// eto znachenie ushe vibiralos val_count++; temp_cand[temp_val]=0; if(Unic_RCM(tempi,tempj, temp_val+1)==1) {board[tempi][tempj]=temp_val+1; start[tempi][tempj]=temp_val+1; break; } } if(Rall_number<=50) {cout<<endl<<"Rall_number="<<Rall_number; if(val_count==8) Step1(); //rekursija else Step2(); // popitka reshenija } else {if(cont<30) {Rall_number=0; cout<<endl<<"cont="<<cont;//getch(); for(i=0;i<15;i++) {tempi=random(9); tempj=random(9); start[tempi][tempj]=0; } cont++; Step1(); } cout<<endl<<"Rall_number="<<Rall_number<<"!!! Stop!!!"; } } void Step2(void) {int i,j,k1,k2; // cout<<endl<<"position:"<<tempi<<" "<<tempj; //cout<<endl<<"val -= "<<board[tempi][tempj]<<endl; for(i=0;i<9;i++) for(j=0;j<9;j++) Cand_Init(mesh[i][j]); for(i=0;i<9;i++) for(j=0;j<9;j++) if (board[i][j]!=0)// v jachejku vpisano chislo {//zapreschaem v stolbtse for(k1=0;k1<9;k1++) mesh[k1][j][board[i][j]-1]=0; //zapreschaem v stroke for(k2=0;k2<9;k2++) mesh[i][k2][board[i][j]-1]=0; // sektor for(k1=(i/3)*3;k1<(i/3)*3+3;k1++) for(k2=(j/3)*3;k2<(j/3)*3+3;k2++) mesh[k1][k2][board[i][j]-1]=0; //sozdaem masku jachejki (i,j) for(k1=0;k1<9;k1++) mesh[i][j][k1]=0; mesh[i][j][board[i][j]-1]=1; } //jachejki, gde vse chisla zaprescheni int flag=0, t=0; for(i=0;i<9;i++) for(j=0;j<9;j++) if (Cand_Count(mesh[i][j])==0) flag++; if (flag!=0) //net reshenija {cout<<endl<<"Net reshenija! Otkat poslednego izmenenija!"<<endl; start[tempi][tempj]=0; Rall_number++; Step1(); } else {for(i=0;i<9;i++) for(j=0;j<9;j++) if (Cand_Count(mesh[i][j])==1) {//podstavliajem tsifru na dosku board[i][j]=Cand_to_Number(mesh[i][j]); t++; } int number; //prosmatrivaem stroki for(i=0;i<9;i++) for(number=0;number<9;number++) {flag=0; for(j=0;j<9;j++) if(mesh[i][j][number]==1) flag++; if(flag==1)//nashli tolko odno vozmozhnoje mesto for(j=0;j<9;j++) if(mesh[i][j][number]==1) {board[i][j]=number+1; t++;} } //prosmatrivaem stolbtsi for(j=0;j<9;j++) for(number=0;number<9;number++) {flag=0; for(i=0;i<9;i++) if(mesh[i][j][number]==1) flag++; if(flag==1) for(i=0;i<9;i++) if (mesh[i][j][number]==1) {board[i][j]=number+1; t++;} } // prosmatrivaem sectora for(int a=0;a<9;a=a+3) for(int b=0;b<9;b=b+3) //eto perebiraem vse sectora { for(number=0;number<9;number++) {flag=0; for(i=(a/3)*3;i<(a/3)*3+3;i++) for(j=(b/3)*3;j<(b/3)*3+3;j++) if(mesh[i][j][number]==1) flag++; if(flag==1) for(i=(a/3)*3;i<(a/3)*3+3;i++) for(j=(b/3)*3;j<(b/3)*3+3;j++) if(mesh[i][j][number]==1) {board[i][j]=number+1; t++;} } } //schitaem skolko mest zapolneno v matritse flag=0; for(i=0;i<9;i++) for(j=0;j<9;j++) if (board[i][j]==0) flag++; cout<<endl<<"Not opened cells:"<<flag; cout<<"\nt="<<t<<endl; if((flag>0)&&(flag<81)&&(old_opened!=flag)) { old_opened=flag; cout<<"\nGOTO Step2"; Step2(); } else if((flag>0)&&(flag<81)&&(old_opened==flag)) {old_opened=flag; cout<<"\nGOTO Step1"; Step1(); } } } void main(void) { randomize(); Init_9_9(start); Init_9_9(roll); Init_9_9(board); cout<<endl; int t,i,j; for(i=0;i<9;i++) for(j=0;j<9;j++) Cand_Init(mesh[i][j]); //Step1(); cout<<endl<<"Maski"<<endl; for(i=0;i<9;i++) {for(j=0;j<9;j++) {if(board[i][j]!=0) t=Unic_RCM(i,j,board[i][j]); else t=8; cout<<t<<" "; } cout<<endl; } getch(); cout<<endl<<"Setka"<<endl; for(i=0;i<9;i++) {for(j=0;j<9;j++) {//t=Unic_RCM(i,j,2); for(int k1=0;k1<9;k1++) cout<<mesh[i][j][k1]; cout<<" "; } cout<<endl; } getch(); Step1(); //schitaem skolko mest zapolneno v matritse int flag=0; for(i=0;i<9;i++) for(j=0;j<9;j++) if (board[i][j]==0) flag++; cout<<endl<<"Opened cells:"<<flag; //schitaem skolko mest zapolneno v matritse flag=0; for(i=0;i<9;i++) for(j=0;j<9;j++) if (board[i][j]!=0) flag++; cout<<endl<<"Passed cells:"<<flag; cout<<"Task:"<<endl; for(i=0;i<9;i++) {for(j=0;j<9;j++) cout<<start[i][j]<<" "; cout<<endl; } cout<<"Solve:"<<endl; for(i=0;i<9;i++) {for(j=0;j<9;j++) cout<<board[i][j]<<" "; cout<<endl; } getch(); // Step1(); getch(); }