Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Trang 2 trên tổng số 2 Đầu tiênĐầu tiên 12
Từ 11 tới 17 trên tổng số 17 kết quả

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

  1. #11
    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

    uh, minh cam on bạn, khi nào được thì bạn cop len cho minh nha
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

  2. #12
    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 Học Hỏi Xem bài viết
    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 đó)
    1. Backtracking chỉ là một kỹ thuật, dùng truy ngược. Sodoku cấp 9 là chịu. Vì bản chất Backtracking là quay lui đệ quy. Xét bao nhiêu trường hợp đây tự tính.
    2. Giả sử người ta cần xây dựng Sodoku cấp 20 chẳng hạn. Nếu dùng cách 2 xóa đi lấy đâu Sodoku cấp 20 ban đầu mà xóa @@.

    Ta luôn sinh được 1 Sodoku cấp n với công thức xác định như sau.

    S[i,j]=k;
    k=(i+j-1)%(n+1);
    if (k==0) k++

    Soduku sinh ra có dạng:
    1 2 3 ... n
    n 1 2 ... n-1
    n-1 n 1 ... n-2
    ....
    n n-1 n-2 ... 1

    Với chữ số từ 1->n.
    Chỉ số hàng,cột tính từ 1.

    Ví dụ :
    Ví trí hàng 5 cột 3 trong Sodoku cấp 6 cơ bản trên là
    k=(5+3-1)%(6+1)=0
    vì k=0 nên k=k+1=0+1=1.
    Vậy S[5,3]=1.

    Không tin thì các bạn có thể thử nghiệm với cấp bất kỳ.

    Từ đó có thể hoán vị các hàng ,cột để sinh ra các Sodoku khác.

    Còn giải Sodoku thì theo tư tưởng nêu trên.

    Xin lỗi vì công thức sinh Sodoku ở trên của mình bị sai.
    Dưới đây là mã chương trình và công thức mình đã chỉnh lại phát sinh Sodoku cơ bản, từ đó sinh ra Sodoku ngẫu nhiên.
    Mã đã kiểm tra trên VC++ 2008

    C++ Code:
    1. #include <iostream>
    2. #include <iomanip>
    3. #include <ctime>
    4. #include <cstdlib>
    5. #include <cstdio>
    6. #include <conio.h>
    7.  
    8. using namespace std;
    9. #define MAX 20
    10.  
    11. //Creating a base Sododu with rank
    12. void CreateBaseSodoku(int rank,int **&Sodoku)
    13. {
    14.     //Alloc Memory for Sodoku
    15.     Sodoku=new int*[rank];
    16.     for (int i=0;i<rank;i++)
    17.     {
    18.         Sodoku[i]=new int[rank];
    19.         for (int j=0;j<rank;j++)
    20.             //This is the formula to determining the value o cell at row i,column j
    21.             //on Sodoku
    22.             Sodoku[i][j]=(i+j)%rank+1;
    23.     }
    24. }
    25.  
    26. //Show up Sodoku
    27. void Show(int rank,int **Sodoku)
    28. {
    29.     if (Sodoku==NULL)
    30.     {
    31.         cout<<"Error, Sodoku wasn't initialized properly\n";
    32.         return;
    33.     }
    34.     for (int i=0;i<rank;i++)
    35.     {
    36.         for (int j=0;j<rank;j++)
    37.             cout<<setw(3)<<Sodoku[i][j];
    38.         cout<<endl;
    39.     }
    40. }
    41.  
    42. //Generate randome Sodoku base on basice Sodoku
    43. //Input is based Sodoku
    44. void RandomSodoku(int rank,int **&Sodoku)
    45. {
    46.  srand((unsigned)time(NULL));
    47.  int row1=rand()%rank;
    48.  int row2=rand()%rank;
    49.  int col1=rand()%rank;
    50.  int col2=rand()%rank;
    51.  //Swapping row1 with row2
    52.  for (int i=0;i<rank;i++)
    53.  {
    54.      swap(Sodoku[row1][i],Sodoku[row2][i]);
    55.  }
    56.  //Swapping col1 with col2
    57.  for (int i=0;i<rank;i++)
    58.  {
    59.      swap(Sodoku[i][col1],Sodoku[i][col2]);
    60.  }
    61. }
    62.  
    63. void main()
    64. {
    65.     int **Sodoku=NULL;
    66.     int rank=0;
    67.     cout<<"Enter rank of sodoku = ";
    68.     cin>>rank;
    69.     cout<<"Base Sodoku\n";
    70.     CreateBaseSodoku(rank,Sodoku);
    71.     Show(rank,Sodoku);
    72.     while (getch()!=27)
    73.     {
    74.      cout<<"Randome Sodoku  (Press Esc to quit) \n";
    75.      RandomSodoku(rank,Sodoku);
    76.      Show(rank,Sodoku);
    77.     }
    78.     system("pause");
    79.  
    80. }

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

    anh Tadius ơi, em cop bài trên của anh về ko chạy dc, em dùng VC 6.0

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

    tất nhiên là được em, vì anh tự viết hết mà

    anh share cho em file giải thích, vi cái này anh làm đề tài cuối kì rồi nên ghi vô nhiều quá

    giải thích nhu sau:
    Attached Files Attached Files

  5. #15
    Ngày gia nhập
    12 2009
    Nơi ở
    bế quan tu lại
    Bài viết
    846

    tadius đã nói kiểm tra trên VC++ 2008 tức là dùng compiler VC++ 2008, vui lòng để ý các compiler của người viết code trước khi comment lung tung vậy nhá

  6. #16
    Ngày gia nhập
    11 2011
    Bài viết
    1

    Mặc định Một cách để giải bài toán sudoku

    Trích dẫn Nguyên bản được gửi bởi Tadius Xem bài viết
    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.
    Ngày trước mình từng lập chương trình phát sinh sudoku và giải sudoku, nhưng trên pascal. Lâu rồi chương trình thất lạc mất. Mình nhớ thuật toán như sau:
    *Thuật toán giải sudoku:
    Với mỗi ô (i,j) đếm số khả năng điền các số vào sao cho không gây mâu thuẫn (tức là không có hàng nào, cột nào, vùng nào có 2 số giống nhau). Đơn giản là ta xét lần lượt các số, nếu trên hàng, trên cột và trong vùng chứa ô đó chưa có số này thì ta có thêm 1 khả năng điền. Ta gọi đó là bậc có thể điền của số (i,j).
    Trên mỗi hàng i, xét khả năng điền của số k, tức là số ô trên hàng i còn trống có thể điền số k vào mà không gây mâu thuẫn. Ta gọi đó là bậc hàng (i,k).
    Tương tự ta xây dựng bậc cột (j,k) và bậc vùng (z,k).
    Tìm trong tất cả 4 loại trên, tìm bậc nhỏ nhất. Ta điền từ ô này. Thử tất cả các giá trị của số điền vào (nếu là bậc điền), hoặc thử điền số vào tất cả các ô có thể (nếu là bậc hàng, bậc cột hoặc bậc vùng). Tiếp tục tính lại các giá trị trên và chọn bậc bé nhất. Nếu điền xong thì thông báo kết quả, nếu tính ra có bậc bằng 0 (tức không điền được nữa), thì quay lui, xóa giá trị vừa điền và điền lại giá trị khác (hoặc điền giá trị vào ô khác).
    Thời gian giải với kích thước bảng sudoku (100x100) là chấp nhận được. Tất nhiên bảng càng dễ giải (tức có càng nhiều bậc 1 - bậc 1 thì chỉ có 1 khả năng để lựa chọn) thì giải càng nhanh.

    Thuật toán sinh bảng sudoku ngẫu nhiên như sau:
    - Bước 1: Điền 1 bảng sudoku nào đó (dùng quay lui kết hợp với sinh số ngẫu nhiên để điền, cũng có thể dùng ngay thuật toán giải sudoku ở trên kết hợp với ngẫu nhiên).
    - Bước 2: Lần lượt bớt 1 số ô ngẫu nhiên nào đó (tức là xóa số đó trên bảng vừa điền). Dùng thuật toán trên giải bảng sudoku thu được. Nếu máy giải được nhiều hơn 1 đáp án thõa mãn thì không bỏ ô này nữa, xét ô khác.
    Rõ ràng, số ô bỏ càng nhiều thì càng khó giải. Trong quá trình giải sudoku, cũng có thể ghi nhận thêm về số khả năng lựa chọn (tức là số bậc 1) để tính luôn độ khó. Số khả năng này càng ít thì càng khó phát hiện, thậm chí nếu có lúc không có bậc 1 nào thì người chơi phải lựa chọn 1 trong 2 hoặc kết hợp nhiều kiểu suy luận khác để giải, do đó sẽ khó hơn.

    Cho 1 bảng sudoku cho trước, bạn có thể hoán vị các số với nhau (ví dụ 1 thành 2, 2 thành 5,...) và điền lại vào bảng thì sẽ thành bảng sudoku mới. Nhưng nếu bạn hoán vị các hàng hoặc các cột với nhau thì mình nghĩ trong đa số trường hợp sẽ không tạo được sudoku mới. Chẳng hạn trong bảng sudoku cơ bản ta phải đảm bảo mỗi hàng, mỗi cột và mỗi vùng 3x3 có đủ các số từ 1 đến 9, nếu bạn hoán vị các hàng hoặc các cột thì không đảm bảo được cho các vùng 3x3 có đủ các số từ 1 đến 9.

  7. #17
    Ngày gia nhập
    03 2010
    Bài viết
    14

    direct link : link down
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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