Chương trình giải ô số Sudoku _ window AFC

[truongtankhoa]

đây là chương trình do mình viết! ai cần thì tải về xem thử, nó chạy tương đối hoàn thiện , sau khi tải về giải nén và chạy trên C++ 6.0 là có cửa sổ chương trình.

[1990]

anh có thể comment vào các hàm trong bài được ko ạ

[Tadius]

Lần trước Hồi học môn Trí Tuệ Nhân Tạo, có bạn cũng làm đề tài này. Bị mình chém cho tơi bời ở các vấn đề sau:
1. Phát sinh Sodoku cấp n (Bạn dùng thuật toán phát sinh hay là Nạp Sodoku có sẵn)
2. Giải Soduku(Bạn sử dụng thuật toán gì hay lại load bản giải có sẵn tương ứng với từng Sodoku).

[1990]

anh Tadius có thể giúp em về thuật toán được ko ạ, em làm trên MFC

[Tadius]

anh Tadius có thể giúp em về thuật toán được ko ạ, em làm trên MFC

Nói thật với bạn thuật toán phát sinh ra một Sodoku cấp n là NPC khó. Vì thế mà @@.
Còn thuật toán giải thì lại đỡ phức tạp hơn.
Thuật toán giải Sodoku có tư tưởng như sau:

1. Giả sử bạn đang xét hàng cột j. Bạn sẽ lọc ra một tập C gọi là tập các ô số chưa biết (chưa được lật).

2. Với mỗi một phần tử chưa biết trên cột j, phần tử đó nằm ở hàng i ta ký hiệu S[i,j] ta làm như sau:
+ Trên hàng i ta tìm các số chưa biết trên hàng I được tập R. Đem tập R giao với tập C. Tập P=C.R (P=C giao C) là tập chứa các số có thể đặt vào trong ô S[i,j].
+ Với mỗi P ta xem xét tới xác xuất xuất hiện của một chữ số trong P bởi việc tìm ra các phần tử trong các tập P xuất hiện ít nhât. Sau đó sẽ tiến hành điền vào ma trận.

Lặp lại tới khi Sodoku bị lật hết thì thôi

Ví dụ đơn giản Sodoku 4*4: Nguyên bản như sau để sau này tiện so sánh
1 2 3 4
2 3 4 1
3 4 2 1
4 1 2 3

Ta có Sodoku 4*4 chưa giải là:

1 x x x
x x 4 x
x 4 x x
x x x 3

+Xét cột 1 : Tập C[1]={2,3,4} là các số chưa được điền vào cột 1.
-Xét hàng 2: R[2]={1,2,3} là các số chưa được điền trong hàng 2.
-Ta có P[2,1]=C[1] giao R[2] = {2,3} là tập chứa số có thể được điền vào
ô S[2,1]. (S là ma trận Sodoku ở hàng 2, cột 1).
-Xét hàng 3 : R[3]={1,2,3} => P[3,1]={2,3}.
-Xét hàng 4 : R[4]={1,2,4} => P[4,1]={2,4}.

Nhận xét P[2,1]={2,3,}, P[3,1]={2,3}, P[4,1]={2,4}.
Thấy rằng phần số 4 chỉ có thể xuất hiện ở hàng 4 mà thôi. Vậy ta biết điền được S[4,1]=4. Tức là ta có

1 x x x
x x 4 x
x 4 x x
4 x x 3

Cứ thế xét các hàng/cột tiếp theo tới khi hết Sodoku thì thôi.

Sorry về phần thuật toán phát sinh Sodoku rằng mình đã phát biểu nó là NPC khó. Thực ra mình vừa nghĩ ra thuật toán sinh Sodoku với chỉ số hàng,cột tính bắt đầu từ 1 là
Sodoku cơ bản ô S[i,j]=k;

Với k được tính như sau:
k= (i+j-1)%(n+1)
if (k=0) then k=1;

Từ đó có thể hoán vị hàng hoặc cột => Sodoku cấp n có n^2 Sodoku cùng cấp tương đương.

[1990]

em cảm ơn anh nhiều, nhưng anh có thề viết cho em hàm sinh số ngẫu nhiên được ko ạ

[Joker]

Sodoku có thể dùng thuật toán Backtracking để duyệt qua tất cả các trường hợp có thể để giải ô số (cũng có thể dùng để phát sinh ô số bằng cách giải 1 ô số sau đó xóa dần random đến khi xóa tiếp thì sinh ra >1 cách giải thì lấy ô số trước đó)

[1990]

bạn có thể nói rõ hơn được ko? ví dụ đi

[Joker]

Nhà mất mạng giờ đang phải ngồi quán :-S... khi nào có net tớ post code lên đây

[1990]

void dienso(){    int dem=0,lap=1;    int tep,s,so1[9];    for (int r=0;r<9;r++) so1[r]=r+1;    while (lap==1)    {        lap=0;        for (int i=1 ;i<=9;i++)        for (int j=1 ;j<=9;j++)        if (A[i][j]==0)         {            for (int k=0;k<9;k++)             {                tep=so1[k];                if (quetngang(tep,i,j)&&quetdoc(tep,i,j)&&queto(tep,i,j))                 {                  ++dem;                  s=tep;                }            }            if (dem==1)             {                A[i][j]=s;                lap=1;            }        dem=0;s=0;        }    }}void cacsocothedien(int x,int y,int z){    int so1[9];    for (int r=0;r<9;r++) so1[r]=r+1;    int j=0;    for (int h=0;h<9;h++) sokhac[z][h]=0;    for (int k=0;k<9;k++)    if (quetngang(so1[k],x,y)&&quetdoc(so1[k],x,y)&&queto(so1[k],x,y))    {        sokhac[z][j]=so1[k];        j++;    }}void cacsokhac(int a){    int temp=0;    for (int i=0;i<9;i++)     if (sokhac[a][i]!=0) temp++;    so[a]=temp;}  void xuatdulieu(){    int de=1;    for (int i=1;i<=9;i++)    {        for (int j=1;j<=9;j++) D[de++]=A[i][j];    } }void tim(int m){       int k,h;     for (k=1;k<=9;k++)    for (h=1;h<=9;h++)    if (A[k][h]==0)     {           t[0][m]=k;t[1][m]=h;return;    }} int kiemtra(){    for (int i=1;i<=9;i++)    for (int j=1;j<=9;j++)    if (A[i][j]==0) return 0;    return 1;}void xuly(int i){        for (int m=1;m<=9;m++)    for (int n=1;n<=9;n++) B[i][m][n]=A[m][n];    tim(i);    cacsocothedien(t[0][i],t[1][i],i);    cacsokhac(i);     if (so[i]!=0)    for (int l=0;l<so[i];l++)    {        if (ktra==1) return;        for (int m1=1;m1<=9;m1++)        for (int m2=1;m2<=9;m2++) A[m1][m2]=B[i][m1][m2];        if (sokhac[i][l]!=0)        {        c1=t[0][i];c2=t[1][i];                A[c1][c2]=sokhac[i][l];        dienso();        if (kiemtra()==1)         {           xuatdulieu();ktra=1;        }        if (kiemtra()==0)  xuly(i+1);        }    }               }

bạn nào có thể giải thích cho minh biết những hàm trên trong bài giải sudoku dùng để làm j được ko ạ, nếu comment vào từng dòng thì càng tốt