#include<iostream.h>

#include<string.h>

#include<conio.h>

#include<stdio.h>

#include<stdlib.h>

int tamij[2][81],th=1,i,j,tang,so[81],a=0;

char kt1[2]="c",kt[2]="c",A[9][9],so_khac[81][9],***B;

void wellcome();

int ss_ngang(char a,int b);

int ss_doc(char a, int b);

int ss_o(char a, int b,int c);

int kiem_tra();

void nhap();

void in();

void dien_so();

void tim_o_trong(int a);

void tim_so_khac(int a, int b,int c);

void so_co_the_dien(int a);

void dien_tiep(int a);

void main(){

while(kt[0]=='c'||kt[0]=='C'){

wellcome();

cin>>kt;

if(kt[0]=='c'||kt[0]=='C'){

// Nhap chuoi thich hop

nhap();

//dien nhung so thich hop

dien_so();

//kiem tra dung sai sau khi dien

if(kiem_tra()==1){

cout<<"

Co duy nhat 1 dap an: ";

in();

getch();

};

if(kiem_tra()==0){

a=0;

// tao mang dong

B=new char** [81];

for(int q=0;q<81;q++)

B[q]=new char* [9];

for(int w=0;w<81;w++)

for( int r=0;r<9;r++)

B[w][r]=new char [9];

dien_tiep(a);

};

};

};

};

void wellcome(){

clrscr();

cout<<"CHUONG TRINH GIAI TRO CHOI \"SUDOKU\"";

cout<<"

Ban nhap vao tung hang ngang voi o khong co so ban hay nhap dau cham";

cout<<"

Ban co muon giai o \"SUDOKU\" nao khong (c/k):";

};

void nhap(){

int t=0;

char chuoi[10];

cout<<"

";

for(int i=0;i<9;i++){

cout<<"nhap mot chuoi:";

gets(chuoi);

for (int j=0;j<9;j++){

A[t][j]=chuoi[j];

chuoi[j]=' ';

};

chuoi[9]=' ';

t++;

};

};

void in(){

cout<<"

";

for (int i=0;i<9;i++)

for (int j=0;j<9;j++){

if(j==3||j==6)cout<<" ";

cout<<A[i][j];

if (j==8) cout<<"

";

if((i==2||i==5)&j==8)cout<<"

";

};

};

void dien_so(){

char tam,tam2,so[]="123456789";

int lap,khac=0;

lap=1;

while (lap==1){

lap=0;

for (int i=0;i<9;i++)

for( int j=0;j<9;j++){

if (A[i][j]=='.'){

for (int k=0;k<9;k++){

tam=so[k];

if((ss_ngang(tam,i)==1)&&(ss_doc(tam,j)==1)&&(ss_o(tam,i,j)==1))

{

tam2=tam;

khac++;

};

};

if(khac==1){

A[i][j]=tam2;

lap=1;

};

};

tam=' ';tam2=' ';khac=0;

};

};

};

int ss_ngang(char a, int b){

int tam=1;

for (int i=0;i<9;i++)

if (a==A[b][i]) tam=0;

return tam;

};

int ss_doc(char a,int b){

int tam=1;

for (int i=0;i<9;i++)

if (a==A[i][b]) tam=0;

return tam;

};

int ss_o(char a, int b, int c){

int tam=1;

if (b<3&&c<3){

for (int i=0;i<3;i++)

for (int j=0;j<3;j++)

if (a==A[i][j]) tam=0;

};

if (b<3&&c>2&&c<6){

for (int i=0;i<3;i++)

for (int j=3;j<6;j++)

if (a==A[i][j]) tam=0;

};

if (b<3&&c>5&&c<9){

for (int i=0;i<3;i++)

for (int j=6;j<9;j++)

if (a==A[i][j]) tam=0;

};

if (b>2&&b<6&&c<3){

for (int i=3;i<6;i++)

for (int j=0;j<3;j++)

if (a==A[i][j]) tam=0;

};

if (b>2&&b<6&&c>2&&c<6){

for (int i=3;i<6;i++)

for (int j=3;j<6;j++)

if (a==A[i][j]) tam=0;

};

if (b>2&&b<6&&c>5&&c<9){

for (int i=3;i<6;i++)

for (int j=6;j<9;j++)

if (a==A[i][j]) tam=0;

};

if (b>5&&b<9&&c<3){

for (int i=6;i<9;i++)

for (int j=0;j<3;j++)

if (a==A[i][j]) tam=0;

};

if (b>5&&b<9&&c>2&&c<6){

for (int i=6;i<9;i++)

for (int j=3;j<6;j++)

if (a==A[i][j]) tam=0;

};

if (b>5&&b<9&&c>5&&c<9){

for (int i=6;i<9;i++)

for (int j=6;j<9;j++)

if (a==A[i][j]) tam=0;

};

return tam;

};

int kiem_tra(){

char tam='.';

int kq=1;

for(int i=0;i<9;i++)

for (int j=0;j<9;j++)

if(tam==A[i][j]) kq=0;

return kq;

};

void tim_o_trong(int a){

tang=0;

for (int i=0;i<9;i++)

for(int j=0;j<9;j++)

if (A[i][j]=='.')

{

tang++;

for(int e=0;e<2;e++)

for(int f=0;f<tang;f++){

if(e==0) tamij[0][a+tang-1]=i;

if(e==1) tamij[1][a+tang-1]=j;

};

};

for(int g=a+1;g<81;g++)

{

tamij[0][g]=0;

tamij[1][g]=0;

};

};

void tim_so_khac( int a, int b,int c){

char so[]="123456789";

int cho_dien=0;

for(int i=0;i<9;i++)

so_khac[c][i]='0';

for (int k=0;k<9;k++){

if((ss_ngang(so[k],a)==1)&&(ss_doc(so[k],b)==1)&&(ss_o(so[k],a,b)==1))

{

cho_dien++;

so_khac[c][cho_dien-1]=so[k];

};

};

};

void so_co_the_dien(int a){

int tang1=0;

for(int i=0;i<9;i++){

if(so_khac[a][i]!='0') tang1++;

so[a]=tang1;

};

};

void dien_tiep(int a){

for(int t=0;t<9;t++)

for(int u=0;u<9;u++)

B[a][t][u]=A[t][u];

tim_o_trong(a);

tim_so_khac(tamij[0][a],tamij[1][a],a);

so_co_the_dien(a);

if(so[a]!=0&&(kt1[0]=='c'||kt1[0]=='C')){

for(int x=0;x<so[a];x++){

for(int w=0; w<9;w++)

for(int r=0; r<9; r++)

A[w][r]=B[a][w][r];

if(so_khac[a][x]!='0'&&(kt1[0]=='c'||kt1[0]=='C')){

i=tamij[0][a];

j=tamij[1][a];

A[i][j]=so_khac[a][x];

dien_so();

if(kiem_tra()==1){

cout<<"

Truong hop "<<th<<" la:

";

th++;

in();

cout<<"

Ban co muon xem tiep truong hop khac khong (c/k):";

cin>>kt1;

};

if(kiem_tra()==0){

dien_tiep(a+1);

};

};

};

};

};