Giải trò Sudoku (Slide)

ĐẠ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ỤC LỤC GIỚI THIỆU VỀ SUDOKU THUẬT TOÁN GIAO DIỆN 1. GIỚI THIỆU VỀ SUDOKU 1. GIỚI THIỆU VỀ SUDOKU(tt) Sudoku là một trò chơi trí tuệ Ra đời tại Nhật Có rất nhiều dạng 9x9, 3x3, 6x6, 16x16, 25x25,… Dạng chuẩn 9x9: 9 dòng, 9 cột, 9 phân vùng nhỏ 1. GIỚI THIỆU VỀ SUDOKU(tt) Luật chơi: Dựa vào gợi ý là các số có sẵn trong đề Sudoku, ta tiến hành điền vào các ô trống còn lại một số trong dãy số từ 1 đến 9, sao cho ở mỗi dòng, mỗi cột, mỗi vùng không có số nào bị lặp lại Phân tích bài toán Xác định: Input: Đề sudoku Output: Đáp án 2. THUẬT TOÁN Sử dụng thuật toán suy diễn lùi 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 Đó 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. 2. THUẬT TOÁN (tt) 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 2. THUẬT TOÁN (tt) Các vấn đề đặt ra: Đánh dấu các khả năng điền số và loại bỏ bớt các khả năng bất khả thi Khử đệ quy cho thuật toán Giải quyết vấn đề 1 Khởi tạo tất cả các ô đều có 9 khả năng điền 1..9 Tạo stack lưu các ô đã điền Thực hiện việc đánh dấu trên ô[i,j] row[i ,newvalue]=0 column[j, newvalue]=0 area[AREA[i,j], newvalue]=0 Đặt giá trị ở ô [i,j] Agree[i,j,0]=1 Agree[i,j,1]=newvalue value[i,j]=1 - Trên hàng, cột, vùng chứa ô [i,j] đó ta loại khả năng điền số newvalue ra khỏi tập khả năng Giải quyết vấn đề 1 (tt) Ví dụ: Ô [3,4] điền số 1 Giải quyết vấn đề 1 (tt) Tìm số chưa được xét đưa vào stack và xử lý như trên cho đến khi không tìm thấy ô nào nữa. Đó là các ô thỏa: - Là ô duy nhất của hàng (cột, vùng) có thể điền một số nào đó - Là ô chỉ có một khả năng điền Giải quyết vấn đề 1 (tt) Ô X là ô duy nhất có thể điền số 5 Ô X là ô chỉ có một khả năng điền số 7 Giải quyết vấn đề 2 Để khử đệ quy của thuật toán ta sử dụng biến điều khiển: Add=1 : tiến Add=-1: lùi Biến index là vị trí hiện tại Giải quyết vấn đề 2 (tt) 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ó. 3. GIAO DIỆN 3. GIAO DIỆN (tt) 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 Solve : thực hiệ việc giải đề sudoku Backward : quay lại đáp án trước đó (nếu đề sudoku có nhiều đáp án) 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 3. GIAO DIỆN (tt) Skins: thay đổi giao diện chương trình Help: Giới thiệu luật chơi About: Giới thiệu thông tin nhóm 3. GIAO DIỆN (tt) Nạp đề: Nhập từng số vào Mở đề từ file Đáp án 3. GIAO DIỆN (tt) Cám ơn sự theo dõi của các bạn!