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 ô. | ĐẠ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 | ĐẠ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 19 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
