Bạn xem bài này mình làm lâu quá rồi nên chưa để ý tới chuyện tối ưu:
#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<<"\nCo 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<<"\n\nBan nhap vao tung hang ngang voi o khong co so ban hay nhap dau cham";
cout<<"\n\nBan co muon giai o \"SUDOKU\" nao khong (c/k):";
};
void nhap(){
int t=0;
char chuoi[10];
cout<<"\n\n\n";
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<<"\n";
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<<"\n";
if((i==2||i==5)&j==8)cout<<"\n";
};
};
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<<"\nTruong hop "<<th<<" la:\n";
th++;
in();
cout<<"\n\nBan co muon xem tiep truong hop khac khong (c/k):";
cin>>kt1;
};
if(kiem_tra()==0){
dien_tiep(a+1);
};
};
};
};
};