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

[thanhtruc02]

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

[thuyduong]

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.

[gaukhunglong]

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

[tungns]

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:

[seo3m]

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á

[vthao93hp]

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.