zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Công nghệ thông tin

Đề tài báo cáo khoa học: Các hệ tri thức - Đề tài: giải trò sudoku

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

Báo xấu

139
lượt xem 25
download

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

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 ô...

Chủ đề:

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

Lưu

Nội dung Text: Đề tài báo cáo khoa học: 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
MỤC LỤC 1. GIỚI THIỆU VỀ SUDOKU 2. THUẬT TOÁN 3. 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: 1.Đá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 2.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Ó THỂ BẠN MUỐN DOWNLOAD

TL.01: Bộ Tiểu Luận Triết Học

207 tài liệu

1486 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.