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

[1990]

uh, minh cam on bạn, khi nào được thì bạn cop len cho minh nha

[Tadius]

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

#include <iostream>#include <iomanip>#include <ctime>#include <cstdlib>#include <cstdio>#include <conio.h> using namespace std;#define MAX 20 //Creating a base Sododu with rankvoid CreateBaseSodoku(int rank,int **&Sodoku){    //Alloc Memory for Sodoku    Sodoku=new int*[rank];    for (int i=0;i<rank;i++)    {        Sodoku[i]=new int[rank];        for (int j=0;j<rank;j++)            //This is the formula to determining the value o cell at row i,column j             //on Sodoku            Sodoku[i][j]=(i+j)%rank+1;    }} //Show up Sodokuvoid Show(int rank,int **Sodoku){    if (Sodoku==NULL)    {        cout<<"Error, Sodoku wasn't initialized properly\n";        return;    }    for (int i=0;i<rank;i++)    {        for (int j=0;j<rank;j++)            cout<<setw(3)<<Sodoku[i][j];        cout<<endl;    }} //Generate randome Sodoku base on basice Sodoku//Input is based Sodokuvoid RandomSodoku(int rank,int **&Sodoku){ srand((unsigned)time(NULL)); int row1=rand()%rank; int row2=rand()%rank; int col1=rand()%rank; int col2=rand()%rank; //Swapping row1 with row2 for (int i=0;i<rank;i++) {     swap(Sodoku[row1][i],Sodoku[row2][i]); } //Swapping col1 with col2 for (int i=0;i<rank;i++) {     swap(Sodoku[i][col1],Sodoku[i][col2]); }} void main(){    int **Sodoku=NULL;    int rank=0;    cout<<"Enter rank of sodoku = ";    cin>>rank;    cout<<"Base Sodoku\n";    CreateBaseSodoku(rank,Sodoku);    Show(rank,Sodoku);    while (getch()!=27)    {     cout<<"Randome Sodoku  (Press Esc to quit) \n";     RandomSodoku(rank,Sodoku);     Show(rank,Sodoku);    }    system("pause"); }

[1990]

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

[truongtankhoa]

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:

[aydada]

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á

[copaiting]

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.

[anhhat]

direct link : link down