Phần mềm C++ | Chương trình giải Sodoku

[mushu]

Có vài bạn em cứ thích chơi trò này chứ em đâu chơi.
Nhưng có người hỏi em nên em tò mò hỏi rõ luật chơi và em có ý tường viết chương trình để giải.
Nói vui tí là chuyến này chẳng ai cho trò sodoky nữa vì em test bản demo thời gian giải chỉ mất < 45 ms thôi.
Ý tưởng của em là đưa ra tất cả các trường hợp và kiểm tra xem nó có phù hợp không.
Mọi người chờ em code xong bản chính thức bằng C++ nhé.

[hacker_mubaohiem]

Uh! rất hân hạnh.Loại này liên quan rất nhiều tới tính chất của matrix đó nhé.
Bạn phải dùng thuật toán nào nhanh ơi là nhanh mới thú vị.Chứ quay lui vét cạn thì thôi . .

>>Tiện thể hỏi:Bạn đo thời gian chạy chương trình = cách nào vậy?Phức tạp và chính xác ko?

[babe]

Cái này dễ mà , hơn nữa chương trình giải sodoku có từ lâu rùi mà trò này có sập đâu
Cách đo thời gian chạy thì đầu chương trình mình lấy system time 1 phát , cuối chương trình lấy phát nữa rồi trừ đi nhau là xong mà

[Forlorn_hope]

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

[ngocnhanctu]

có bác nào biết cách viết chương trình chuyển đổi từ so tự nhiên sang hệ nhị phân khong ?????????????????

[DKhanh]

Mình viết trò này cách đây 3 năm dùng phương pháp try and error thấy cũng nhanh mà, cái nào cũng giải ra được chưa tới 1s. Còn không thì có thể dùng luật của sudoku . Hoặc dùng thuật toán Dancing Link là nhanh nhất, nhưng cài đặt khó.