Báo cáo các hệ tri thức - đề tài: giải trò sudoku

Chia sẻ: Lê Tẹt | Ngày: | Loại File: DOC | Số trang:36

Thêm vào BST

Báo xấu

379
lượt xem 58
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với những kiến thức đã đạt được trong quá trình học tập và nghiên cứu môn học này chúng tôi lựa chọn đề tài Giải trò sudoku để vận dụng những kiến thức đó vào lập trình. Đề tài Giải trò sudoku này sử dụng ngôn ngữ lập trình C# để thể hiện các thuật toán Heuristic và Suy diễn lùi (Backtracking) bằng công cụ lập trình Microsoft Visual Studio 2010 nhằm tạo ra một chương trình Giải trò Sudoku thân thiện, dễ sử dụng và giải được các đề sudoku một cách chính xác....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo các hệ tri thức - đề tài: giải trò sudoku

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN  KHOA HỆ THỐNG THÔNG TIN BÁO CÁO CÁC HỆ CƠ SỞ TRI THỨC ĐỀ TÀI: GIẢI TRÒ SUDOKU
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN  KHOA HỆ THỐNG THÔNG TIN BÁO CÁO CÁC HỆ CƠ SỞ TRI THỨC ĐỀ TÀI: GIẢI TRÒ SUDOKU
MỞ ĐẦU Môn học Các hệ cơ sở tri thức cung cấp những kiến thức cơ bản về các hệ cơ sở tri thức bao gồm: - Tổ chức tri thức - Các cơ chế và kỹ thuật lập trình - Động cơ suy diễn, logic mờ,… Với những kiến thức đã đạt được trong quá trình học tập và nghiên cứu môn học này chúng tôi lựa chọn đề tài Giải trò sudoku để vận dụng những kiến thức đó vào lập trình. Đề tài Giải trò sudoku này sử dụng ngôn ngữ lập trình C# để thể hiện các thuật toán Heuristic và Suy diễn lùi (Backtracking) bằng công cụ lập trình Microsoft Visual Studio 2010 nhằm tạo ra một chương trình Giải trò Sudoku thân thiện, dễ sử dụng và giải được các đề sudoku một cách chính xác.
LỜI CẢM ƠN Thông qua báo cáo này chúng tôi xin gửi lời cám ơn chân thành đến các thầy cô, bạn bè đã giúp đỡ trong quá trình học tập, nghiên cứu và xây dựng chương trình này! Đặc biệt gửi lời cám ơn đến thầy Nguyễn Đình Thuân – giáo viên giảng dạy - đã tận tình truyền dạy những kiến thức cần thiết và giải đáp các thắc mắc trong suốt quá trình học tập môn Các hệ cơ sở tri thức này!
NHẬN XÉT (của giáo viên hướng dẫn) ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................ ................................................................................................................................................
MỤC LỤC MỞ ĐẦU.................................................................................................................................................... 3 LỜI CẢM ƠN........................................................................................................................................... 4 NHẬN XÉT................................................................................................................................................ 5 MỤC LỤC................................................................................................................................................. 6 CHƯƠNG 1: PHÂN TÍCH BÀI TOÁN................................................................................................... 1 1.1 GIỚI THIỆU............................................................................................................................1 1.2 MỤC ĐÍCH..............................................................................................................................2 1.3 CÁCH LÀM.............................................................................................................................2 CHƯƠNG 3: PHÂN TÍCH THUẬT TOÁN........................................................................................... 3 3.1 CƠ SỞ LÝ THUYẾT..............................................................................................................3 3.1.1 HEURISTIC......................................................................................................................3 3.1.2 THUẬT TOÁN SUY DIỄN LÙI (BACKTRACKING)..........................................................3 CHƯƠNG 4: CẤU TRÚC DỮ LIỆU...................................................................................................... 5 4.1 BIẾN........................................................................................................................................5 4.2 HÀM........................................................................................................................................6 CHƯƠNG 5: GIAO DIỆN CHƯƠNG TRÌNH.................................................................................... 17 5.1 CÁC THÀNH PHẦN CỦA CHƯƠNG TRÌNH.......................................................................19 5.1.1 THÀNH PHẦN HIỂN THỊ VÀ NHẬP ĐỀ.........................................................................19 5.1.2 TAB HOME....................................................................................................................20 5.1.3 TAB HELP......................................................................................................................22 5.2 MỘT SỐ HÌNH ẢNH KHI CHẠY CHƯƠNG TRÌNH.............................................................23 CHƯƠNG 6: KẾT LUẬN...................................................................................................................... 28 6.1 ĐÁNH GIÁ............................................................................................................................28 6.1.1 ƯU ĐIỂM:......................................................................................................................28 6.1.2 NHƯỢC ĐIỂM:..............................................................................................................28 6.2 HƯỚNG PHÁT TRIỂN.........................................................................................................28 DANH MỤC TÀI LIỆU THAM KHẢO............................................................................................... 29
CHƯƠNG 1: PHÂN TÍCH BÀI TOÁN 1.1 GIỚI THIỆU Sudoku là một trò chơi trí tuệ nổi tiếng, thu hút nhiều người tham gia thuộc nhiều tầng lớp, độ tuổi khác nhau. Sudoku ra đời ở Nhật và không lâu sau đã đó đã nhanh chóng lan rộng trên toàn thế giới. Ngày nay, sudoku có nhiều bản thể khác nhau: 9x9, 3x3, 4x4, 6x6, 5x5, 7x7, 8x8, 16x16, 12x12, 25x25,… Đối với đề tài nay, chúng tôi chỉ áp dụng cho sudoku dạng chuẩn 9x9 Một đề sudoku là một hình vuông, mỗi chiều có 9 ô nhỏ, hợp thành 9 cột, 9 hàng và được chia thành 9 ô lớn 3x3. Một vài ô nhỏ được đánh số, đó là những manh mối duy nhất để bạn tìm lời giải. Tuỳ theo mức độ nhiều hay ít của các manh mối, các câu đố được xếp loại dễ, trung bình, khó hay cực khó. Cách chơi Sudoku khá đơn giản là điền số từ 1 đến 9 vào những ô trống sao cho mỗi cột dọc, mỗi hàng ngang, mỗi phân vùng nhỏ có đủ các từ 1 đến 9 mà không được lặp lại.
1.2 MỤC ĐÍCH Xây dựng một chương trình giải sudoku nhanh chóng và chính xác. 1.3 CÁCH LÀM Cho người chơi nhập vào một đề Sudoku bằng cách nhập từ số hoặc mở từ file *.sdk, *.txt. Sau đó nhấn nút Solve chương trình sẽ đưa ra đáp án cùng với các thông tin khác như đó là đáp án thứ mấy trong tổng số đáp án,…
CHƯƠNG 3: PHÂN TÍCH THUẬT TOÁN 3.1 CƠ SỞ LÝ THUYẾT 3.1.1 HEURISTIC Heuristic là những tri thức được rút tỉa từ những kinh nghiệm, trực giác của con người, nó có thể là những tri thức đúng hoặc sai, là những meta knowledge và thường đúng. Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách giải bài toán với các đặc tính sau: • Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất) • Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn. • Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người. Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta thường dựa vào một số nguyên lý cơ bản như sau: Nguyên lý vét cạn thông minh: Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu. Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải. Nguyên lý thứ tự: Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt. Hàm Heuristic: Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các hàm Heuristic. Đó là các hàm đánh già thô, giá trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được cách hành động tương đối hợp lý trong từng bước của thuật giải. 3.1.2 THUẬT TOÁN SUY DIỄN LÙI (BACKTRACKING) Suy diễn lùi là một chiến lược tìm kiếm lời giải cho các bài toán thỏa mãn ràng buộc.
Các bài toán thỏa mãn ràng buộc là các bài toán có m ột l ời gi ải đ ầy đ ủ, trong đó th ứ t ự c ủa các phần tử không quan trọng. Các bài toán này bao gồm một t ập các bi ến mà m ỗi bi ến c ần được gán một giá trị tùy theo các ràng buộc cụ thể của bài toán. Vi ệc quay lui là để th ử tất c ả các tổ hợp để tìm được một lời giải. Thế mạnh c ủa phương pháp này là nhi ều cài đ ặt tránh được việc phải thử nhiều tổ hợp chưa hoàn chỉnh, và nhờ đó giảm thời gian ch ạy, tìm đ ược nhiều đáp án cho những bài có nhiều cách giải. Đó là một quá trình tìm kiếm theo độ sâu trong m ột tập h ợp các l ời gi ải. Trong quá trình tìm kiếm, nếu ta gặp một hướng lựa chọn không thỏa mãn, ta quay lui v ề đi ểm l ựa ch ọn n ơi có các hướng khác và thử hướng lựa chọn tiếp theo. Khi đã thử hết các lựa ch ọn xu ất phát t ừ điểm lựa chọn đó, ta quay lại điểm lựa chọn trước đó và thử hướng lựa chọn ti ếp theo tại đó. Quá trình tìm kiếm thất bại khi không còn điểm lựa chọn nào nữa. Quy trình đó thường được cài đặt bằng một hàm đệ quy mà trong đó m ỗi th ể hi ện c ủa hàm lấy thêm một biến và lần lượt gán tất cả các giá trị có thể cho biến đó, với mỗi lần gán trị lại gọi chuỗi đệ quy tiếp theo để thử các biến tiếp theo. Chiến lược quay lui tương tự v ới tìm kiếm theo độ sâu nhưng sử dụng ít không gian bộ nhớ hơn, nó ch ỉ l ưu gi ữ tr ạng thái c ủa m ột lời giải hiện tại và cập nhật nó. - Ở một bài toán hiện tại (mỗi nốt), ta đi tìm lời giải cho bài toán đó. Ứng với lời giải, ta đi giải bài toán kế tiếp cho đến khi lúc bài toán gốc trở nên đầy đủ. - Lời giải của bài toán gốc thường là một lối đi từ gốc đến nốt cu ối cùng (không có nốt con). - Người ta thường sử dụng một số phương pháp heuristic để tăng tốc cho quá trình quay lui.
CHƯƠNG 4: CẤU TRÚC DỮ LIỆU 4.1 BIẾN Ta sử dụng các biến kiểu mảng sau: int [,] row = new int[10, 10]; int [,] collum=new int[10,10]; int [,] area=new int[10,10]; int [,] AREA=new int[10,10]; int [,] Area=new int[10,10]; int [,,] agree=new int[10,10,11]; int [,] value=new int[10,10]; int [] stack=new int[500] Trong đó, - Các mảng row, collum, area là các mảng dùng để duyệt qua các dòng, các cột và các vùng, đánh đấu hàng cột, vùng có thể điền được một số nào đó. Giá trị của các biến là 0 là không thể điền và 1 là có thể điền. Ví dụ: row[1,2]=1: có nghĩa là tại dòng 1, ta có thể điền vào số 2 row[2,3]=0: có nghĩa là tại dòng 2, ta không thể điền số 3 collum[3,4]=1: có nghĩa là tại cột 3, ta có thể điền vào số 4 area[5,6]=1: có nghĩa là tại vùng 5, ta có thể điền vào số 6 - Để đánh dấu một ô thuộc vùng nào của sudoku ta dùng mảng AREA. Ví dụ: AREA[4,5]=5: có nghĩa là ô tại hàng 4, cột 5 là thuộc vùng 5. Mảng Area dùng để duyệt theo vùng, với Area[i,j]=k: tại vùng i có ô trống thứ j là k. - Mảng agree dùng để đánh dấu xem một ô trống nào đó có thể điền các giá trị nào. Ví dụ agree[i,j,0] = k nghĩa là ô hàng i, cột j có k khả năng điền vào. Các khả năng đó là agree[i,j,1], agree[i,j,2], agree[i,j,3]… agree[i,j,k]. - Mảng value là mảng 2 chiều để chỉ chỉ số giá trị đang được điền hiện tại của 1 ô bất kỳ. value[i,j] = k nghĩa là ô hàng i, cột j đang được điền số agree[i,j,k]. ví dụ agree[1,2,0] = 5. Có 5 giá trị có thể điền vào ô hàng 1 cột 2 và 5 giá trị đó là:
agree[1,2,1] = 2, agree[1,2,2] = 3, agree[1,2,3] = 5, agree[1,2,4] = 6, agree[1,2,5] = 9 value[1,2] = 3 có nghĩa là ô hàng 1, cột 2 đang được đánh số thứ 3 trong các khả năng có thể điền, tức là ô đó đang được điền vào số 5 4.2 HÀM - Xác định bài toán: Input : Đề Sudoku do người dùng nhập vào hoặc mở từ file *.sdk hoặc *.txt. Một file *.sdk hoặc *.txt sẽ lưu một đề sudoku dưới dạng một ma trận vuông 309000605 000009000 800507003 061030700 000102000 004050310 200801007 000600000 103000406 Hoặc một chuỗi các số 0030501000609000200020013080000000305000600000900006003006009010700030800 01070200 Trong đó:
Số 0: là vị trí các ô trống trong đề sudoku Số khác 0: là vị trị các ô số mà đề cho. Output : Đáp án sudoku. Có thể có nhiều đáp án, hoặc không có đáp án. Cách xác định mỗi ô số bất kỳ. Xác định theo số thứ tự từ 1 đến 81. Cách này ta sẽ sử dụng chủ yếu để duyệt toàn bộ 81 ô, hay để lấy đề bài, xuất kết quả ra giao diện người dùng. Xác định bằng [hàng, cột], với cách xác định này, ta dễ dàng duyệt theo cột theo hàng.
Xác định bằng {vùng, số thứ tự trong vùng}, cách xác địn này cho phép ta duyệt theo vùng.
Các dạng này dễ dàng chuyển đổi qua lại lẫn nhau bởi công thức sau. Chuyển từ dạng 1 sang dạng 2. const int size = 9; int toi(int x) { return (x-1)/size+1; } int toj(int x) { return (x-1)%size+1; } int tox(int x, int y) { return (x - 1) * size + y; } Đối với dạng số 3 thì ta lưu thành mảng AREA để sử dụng, trong mảng này, mỗi giá trị AREA[i,j] = số thứ tự ở dạng 1. Vấn đề.
Chương trình giải dựa trên giải thuật suy diễn lùi. Tư tưởng của giải thuật này là chia nhỏ bài toán lớn thành các bài toán phần tử, giải các bài toán phần tử, ứng với mỗi trường hợp giải được của bài toán phần tử đó, ta tìm lời giải cho bài toán phần tử tiếp theo cho đến khi bài toán lớn được giải quyết. Void Try (int i) { { } } Ta thấy rằng khi đang xét ở vị trí i, ta đưa ra các phương án để tiếp tục xét vị trí i+1, có những phương án sẽ làm cho vị trí i+1, i+2… có thể tìm các phương án và dẫn tới kết quả cuối cùng (gọi là phương án khả thi) và có những phương án sẽ không có kết quả (gọi là phương án bất khả thi). Do đó, để chương trình chạy nhanh, ta cần phải loại bỏ các phương án bất khả thi càng nhiều càng tốt. Thuật toán được biểu diễn bằng đệ quy nhưng nếu ta cài đặt bằng đệ quy thì sẽ không có lợi, phải có bộ nhớ stack, gọi hàm đệ quy nhiều lần, điều đó sẽ làm chương trình chạy rất chậm. Vì vậy ta có thể cài đặt không đệ quy nhưng vẫn giải trên phương pháp đệ quy. Để làm được điều này, cần phải có cách sao cho có thể di chuyển và thử các khả năng trên ô dễ dàng. Giải quyết vấn đề.
Vấn đề 1. Ta đánh dấu các khả năng điền số và tìm cách loại bỏ các khả năng bất khả thi. Các bước làm như sau. Khởi tạo tất cả các ô trống đều có 9 khả năng điền từ 1 đến 9. Tạo một stack để lưu các ô đã điền. Cứ mỗi ô [i,j] đã được điền giá trị New Value, ta tiến hành các thao tác như sau. Đánh dấu trên hàng, cột và vùng chứa ô [i, j] là giá trị New Value đã được điền và không được điền nữa bằng cách đặt các giá trị row[i, NewValue]=0 column[j, NewValue]=0 area[AREA[i,j], NewValue]=0. Đặt giá trị ở vùng [i,j] là
agree[i,j,0] = 1 (chỉ 1 giá trị có thể điền) agree[i,j,1] = NewValue value[i,j] = 1. Với các ô trên hàng, cột, vùng chứa ô đó (tất nhiên phải khác ô đó) ta loại bỏ các khả năng điền số NewValue ra khỏi tập các khả năng. Ví dụ ô [3,4] đã điền số 1 Ta tiến hành tìm số chưa từng được xét đưa vào stack và cũng được xử lý như trên cho đến khi không tìm thấy ô nào nửa. Đó là các ô thỏa mãn, là ô duy nhất của hàng (hoặc cột, hoặc vùng) có thể điền một số nào đó. Ví dụ hàng 4 chỉ có thể điền số 5 tại ô ở cột 6 (dấu x), như vậy ta sẽ xóa khả năng điền được số 5 tại các ô đánh dấu (-).
Là ô chỉ có một khả năng điền. Ví dụ ô [5,6] (đánh dấu x) chỉ có thể điền số 7, do đó các ô đánh dấu (-) có thể loại bỏ số 7 ra khỏi tập phương án.