#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();
}