Đề 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 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 3 0 9 0 0 0 6 0 5 0 0 0 0 0 9 0 0 0 8 0 0 5 0 7 0 0 3 0 6 1 0 3 0 7 0 0 0 0 0 1 0 2 0 0 0 0 0 4 0 5 0 3 1 0 2 0 0 8 0 1 0 0 7 0 0 0 6 0 0 0 0 0 1 0 3 0 0 0 4 0 6 Hoặc một chuỗi các số 003050100060900020002001308000000030500060000090000600300600901070003080001070200 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. Ngoài ra nếu như khi kiểm tra có hàng, cột hay vùng mà không thể điền được một giá trị nào đó thì kết quả sẽ là không có nghiệm. Hoặc có 1 ô nào đó không có khả năng điền, sudoku cũng sẽ không có nghiệm. Vấn đề 2. Khử đệ quy trong thuật toán. Tư tưởng chính, ta sử dụng một biến điều khiển việc di chuyển lên trước, ra sau giữa các ô số. Để việc di chuyển dễ dàng, ta dùng cách xác định ô số thứ nhất. Biến điều khiển add sẽ mang giá trị 1 nếu tiến về phía trước, -1 nếu quay về sau. Biến index để chỉ vị trí hiện tại. Thuật toán cơ bản: Bước 1: index = 1 (đang xét ô 1) add = 1 (đang tiến). Bước 2: Lặp trong khi vị trí tiếp ta xét là lớn hơn 0 Nếu index == 82 (nghĩa là từ ô 1 đến ô 81 đã đúng), ta đưa ra kết quả và thoát. Nếu ô hiện tại chỉ có 1 khả năng thì tiếp tục vòng lặp. Ta không xét những ô này, những ô này luôn có value[,] bằng 1. Nếu ô hiện tại có giá trị chính là giá trị tối đa, nghĩa là không thế tăng lên nữa, thì ta cho nó về giá trị nhỏ nhất, cho add = -1, tiếp tục vòng lặp, lùi về ô trước nó. Ta cần thay đổi giá trị trên ô số hiện thời nên giá trị cũ bị bỏ. Những ràng buộc của giá trị cũ đối với hàng, cột và vùng cũng bị bỏ. Tìm giá trị trong tập khả năng có thể điền cho ô hiện tại, giá trị đó phải chưa được điền trong hàng, cột, vùng chứa nó và lớn hơn hoặc bằng giá trị hiện thời (xây dựng cấu hình sudoku theo chiều hướng tăng). Nếu ở bước trên Tìm thấy giá trị thỏa mãn thì ta tạo ràng buộc đã điền giá trị trong cột, hàng, ô chứa ô số đó. Cho add = 1, sau đó tiếp tục vòng lặp để tiến tới ô phía sau. Nếu không tìm thấy thì ta cho add = -1, tiếp tục vòng lặp ta xét ô liền trước nó. Thực tế, ta không chỉ cần tìm một đáp án mà ta còn phải điếm số đáp án, xem đáp án không phải là đáp án đầu tiên, nên từ thuật toán cơ bản ta có một số điều chỉnh như sau. Ta tạo biến iResultCount để điếm số đáp án đã tìm được, cứ hễ tìm thấy đáp án thì ta tăng biến này lên 1. Ta thêm tham số count cho hàm, tham số về số kết quả. Nếu là -1 tức là điếm số kết quả, gặp tham số này ta không bao giờ xuất kết quả. Khi iResultCount lớn hơn tối đa số kết quả cần tìm hoặc không tìm thấy kết quả nào nữa thì trả về giá trị của iResultCount. Nếu là 0 là in ra kết quả đầu tiên, chương trình sẽ chạy như thuật toán cơ bản. Nếu tìm thấy kết quả, chương trình sẽ xuất ra kết quả đó và trả về giá trị 1, nếu không thấy trả về 0. Nếu là một số dương thì ta sẽ in ra kết quả nếu iResultCount == count. Nếu tìm thấy kết quả chương trình sẽ xuất ra kết quả đó và trả về giá trị 1, nếu không thấy trả về 0. Chương trình giải bao gồm các hàm cơ bản sau: Public clsCoreSDK (int[] _pro): tạo ra đối tượng trên lớp Sudoku, khởi tạo các giá trị cho các biến cần thiết cho các hàm giải. Private bool bInputData(): đưa đề bài có dạng là mảng 2 chiều để khởi tạo các mảng dùng cho việc giải như mảng agree[, ,], mảng value[,]. Ngoài ra hàm cũng phát hiện ra trường hợp đề bài có mâu thuẩn (như trong 1 hàng có 2 ô có cùng giá trị…) lúc đó đề không có đáp án. Public void preSolve(): giải thủ công, bước giải này là để chuẩn bị nhằm hạn chế các trường hợp không dẫn tới đáp án cho hàm giải chính. Int Solve(int count): giải đề bằng thuật toán quay lùi, tham số int count là để điều khiển công việc của hàm như xem đáp án có số thứ tự nào đó, điếm số đáp án. Tùy thuộc tham số count mà hàm sẽ trả về các giá trị khác nhau. Public bool bSolveFirst(): hàm này gọi hàm Solve(0) để tìm ra đáp án đầu tiên. Khi đó hàm Solve(0) sẽ trả về 1 nếu tìm thấy, 0 nếu không tìm thấy. Public bool bSolveTo(int _index): hàm gọi hàm Solve(_index) để giải đến đáp án thứ _index. Public int ResultCount(): hàm gọi hàm Solve(-1) để điếm số đáp án của đề bài. Khi đó hàm Solve sẽ giải cho đến khi không tìm thấy đáp án nào nữa và trả về tổng số đáp án hoặc giải đến đáp án thứ max và kết luận đề có quá nhiểu đáp án trả về -1. CHƯƠNG 5: GIAO DIỆN CHƯƠNG TRÌNH 5.1 CÁC THÀNH PHẦN CỦA CHƯƠNG TRÌNH 5.1.1 THÀNH PHẦN HIỂN THỊ VÀ NHẬP ĐỀ Đây là màn hình hiển thị đáp án sudoku Các nút chức năng bao gồm các nút di chuyển và các nút số giúp cho việc nhập đề sudoku 5.1.2 TAB HOME Tab Home bao gồm các chức năng: New : tạo mới một đề Sudoku. Open : mở một đề sudoku từ file *.sdk hoặc *.txt Save : lưu đáp án dưới thành file *.sdk hoặc *.txt Export: Xuất đề và đáp án sudoku thành file word hoặc html Backward : quay lại đáp án trước đó (nếu đề sudoku có nhiều đáp án) Solve : thực hiện việc giải đề sudoku Forward : đến đáp án tiếp theo (nếu đề sudoku có nhiều đáp án) Restore : khôi phục lại đề sudoku như ban đầu Statistics : thống kê số ô trống, số ô đã điền, tổng số đáp án của một đề sudoku Exit : thoát khỏi chương trình 5.1.3 TAB HELP Skins : cho phép thay đổi giao diện chương trình Help : giới thiệu về luật chơi sudoku About : giới thiệu về nhóm thực hiện chương trình 5.2 MỘT SỐ HÌNH ẢNH KHI CHẠY CHƯƠNG TRÌNH Khi chương trình mới khởi động: Sau khi chương trình khởi động xong, ta thực hiện nạp đề bằng cách nhập từ số hoặc mở từ file Nhấp nút Solve chương trình sẽ thực hiện việc giải đề và hiển thị đáp án đầu tiên Sử dụng nút Backward và Forward để di chuyển qua lại các đáp án Ví dụ như với đề trên thì khi nhấn vào nút Statistics sẽ hiển thị ra thông báo sau: Xuất file: Dạng file word dạng file html Ngoài ra, chương trình còn tích hợp phần nghe nhạc giúp ta có thể vừa nghe nhạc vừa giải đề Với các chức năng cơ bản như: chọn danh sách bài hát, phát bài hát, chuyển qua lại giữa các bài trong list, tạm dừng, dừng hẳng, điều chỉnh volume CHƯƠNG 6: KẾT LUẬN 6.1 ĐÁNH GIÁ Chương trình Giải trò Sudoku đã có những ưu điểm và nhược điểm sau: 6