Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 17 kết quả

Đề tài: Chương trình giải ô số Sudoku _ window AFC

  1. #1
    Ngày gia nhập
    04 2010
    Bài viết
    14

    Mặc định Chương trình giải ô số Sudoku _ window AFC

    đâ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.
    Attached Files Attached Files
    Đã được chỉnh sửa lần cuối bởi truongtankhoa : 10-04-2010 lúc 07:17 PM. Lý do: bổ sung thông tin

  2. #2
    Ngày gia nhập
    04 2009
    Bài viết
    10

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

  3. #3
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    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).

  4. #4
    Ngày gia nhập
    04 2009
    Bài viết
    10

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

  5. #5
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Trích dẫn Nguyên bản được gửi bởi 1990 Xem bài viết
    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.

  6. #6
    Ngày gia nhập
    04 2009
    Bài viết
    10

    Mặc định Chương trình giải ô số Sudoku _ window AFC

    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 ạ

  7. #7
    Ngày gia nhập
    07 2010
    Nơi ở
    HN
    Bài viết
    167

    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 đó)

  8. #8
    Ngày gia nhập
    04 2009
    Bài viết
    10

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

  9. #9
    Ngày gia nhập
    07 2010
    Nơi ở
    HN
    Bài viết
    167

    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

  10. #10
    Ngày gia nhập
    04 2009
    Bài viết
    10

    C Code:
    1. void dienso()
    2. {
    3.     int dem=0,lap=1;
    4.     int tep,s,so1[9];
    5.     for (int r=0;r<9;r++) so1[r]=r+1;
    6.     while (lap==1)
    7.     {
    8.         lap=0;
    9.         for (int i=1 ;i<=9;i++)
    10.         for (int j=1 ;j<=9;j++)
    11.         if (A[i][j]==0)
    12.         {
    13.             for (int k=0;k<9;k++)
    14.             {
    15.                 tep=so1[k];
    16.                 if (quetngang(tep,i,j)&&quetdoc(tep,i,j)&&queto(tep,i,j))
    17.                 {
    18.                   ++dem;
    19.                   s=tep;
    20.                 }
    21.             }
    22.             if (dem==1)
    23.             {
    24.                 A[i][j]=s;
    25.                 lap=1;
    26.             }
    27.         dem=0;s=0;
    28.         }
    29.     }
    30. }
    31. void cacsocothedien(int x,int y,int z)
    32. {
    33.     int so1[9];
    34.     for (int r=0;r<9;r++) so1[r]=r+1;
    35.     int j=0;
    36.     for (int h=0;h<9;h++) sokhac[z][h]=0;
    37.     for (int k=0;k<9;k++)
    38.     if (quetngang(so1[k],x,y)&&quetdoc(so1[k],x,y)&&queto(so1[k],x,y))
    39.     {
    40.         sokhac[z][j]=so1[k];
    41.         j++;
    42.     }
    43. }
    44. void cacsokhac(int a)
    45. {
    46.     int temp=0;
    47.     for (int i=0;i<9;i++)
    48.     if (sokhac[a][i]!=0) temp++;
    49.     so[a]=temp;
    50. }
    51.  
    52.  
    53. void xuatdulieu()
    54. {
    55.     int de=1;
    56.     for (int i=1;i<=9;i++)
    57.     {
    58.         for (int j=1;j<=9;j++) D[de++]=A[i][j];
    59.     }
    60.  
    61. }
    62. void tim(int m)
    63. {  
    64.     int k,h;
    65.  
    66.     for (k=1;k<=9;k++)
    67.     for (h=1;h<=9;h++)
    68.     if (A[k][h]==0)
    69.     {  
    70.         t[0][m]=k;t[1][m]=h;return;
    71.     }
    72. }
    73.  
    74. int kiemtra()
    75. {
    76.     for (int i=1;i<=9;i++)
    77.     for (int j=1;j<=9;j++)
    78.     if (A[i][j]==0) return 0;
    79.     return 1;
    80. }
    81. void xuly(int i)
    82. {
    83.    
    84.     for (int m=1;m<=9;m++)
    85.     for (int n=1;n<=9;n++) B[i][m][n]=A[m][n];
    86.     tim(i);
    87.     cacsocothedien(t[0][i],t[1][i],i);
    88.     cacsokhac(i);
    89.  
    90.     if (so[i]!=0)
    91.     for (int l=0;l<so[i];l++)
    92.     {
    93.         if (ktra==1) return;
    94.         for (int m1=1;m1<=9;m1++)
    95.         for (int m2=1;m2<=9;m2++) A[m1][m2]=B[i][m1][m2];
    96.         if (sokhac[i][l]!=0)
    97.         {
    98.         c1=t[0][i];c2=t[1][i];
    99.        
    100.         A[c1][c2]=sokhac[i][l];
    101.         dienso();
    102.         if (kiemtra()==1)
    103.         {
    104.            xuatdulieu();ktra=1;
    105.         }
    106.         if (kiemtra()==0)  xuly(i+1);
    107.         }
    108.     }              
    109. }

    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

Các đề tài tương tự

  1. Mã nguồn chương trình giải Sudoku rất là tuyệt
    Gửi bởi quanghoa trong diễn đàn Dự án & Source code C#, ASP.NET
    Trả lời: 22
    Bài viết cuối: 27-11-2014, 08:13 PM
  2. Giải thuật Thảo luận giải Sudoku bằng phương pháp suy luận logic
    Gửi bởi BDK trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 1
    Bài viết cuối: 26-03-2014, 11:05 PM
  3. Giải thuật C kiểm tra xem người chơi đã giải xong Sudoku hay chưa
    Gửi bởi phanvanlinhqt trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 2
    Bài viết cuối: 05-10-2013, 06:10 PM
  4. Bài tập C++ Giải sudoku 9x9 bằng thuật toán quay lui?
    Gửi bởi pearl9_dn trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 16
    Bài viết cuối: 13-04-2011, 02:35 PM
  5. Lập trình C++ lỗi giải ô số sudoku trong C?
    Gửi bởi quanganhct trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 12
    Bài viết cuối: 16-03-2011, 09:01 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn