Báo cáo dự án giữa kì Toán tổ hợp và đồ thị: Xây dựng câu đố SUDOKU có nội dung gồm 5 chương trình bày về mô tả bài toán, các bước giải bài toán, code, 5 test case, bảng đánh giá,... Mời các bạn cùng tham khảo!
AMBIENT/
Chủ đề:
Nội dung Text: Báo cáo dự án giữa kì Toán tổ hợp và đồ thị: Xây dựng câu đố SUDOKU
- TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO DỰ ÁN GIỮA KÌ
TOÁN TỔ HỢP VÀ ĐỒ THỊ
Xây dựng Câu đố SUDOKU
Người hướng dẫn: GV. NGUYỄN CHÍ THIỆN
Người thực hiện: NGUYỄN QUỐC THÁI – 51800930
Lớp: 18050301
LƯU QUANG THẮNG – 51800932
Lớp: 18050301
Khoá : 22
1
- THÀNH PHỐ HỒ CHÍ MINH, NĂM 2021
2
- 3
- LỜI CẢM ƠN
Qua đây em xin được gửi lời cảm ơn thầy đã tận tình giúp đỡ, hướng dẫn em
hoàn thành dự án này. Tuy nhiên do trình độ và kiến thức còn hạn hẹp nên trong
chương trình không tránh khỏi những thiếu sót, em rất mong nhận được những góp
ý và bổ sung của các thầy và các bạn để đề tài của em được hoàn thiện.
4
- ĐỒ ÁN ĐƯỢC HOÀN THÀNH
TẠI TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
Tôi xin cam đoan đây là sản phẩm đồ án của riêng chúng tôi và được sự
hướng dẫn của GV. Nguyễn Chí Thiện. Các nội dung nghiên cứu, kết quả trong đề
tài này là trung thực và chưa công bố dưới bất kỳ hình thức nào trước đây. Những
số liệu trong các bảng biểu phục vụ cho việc phân tích, nhận xét, đánh giá được
chính tác giả thu thập từ các nguồn khác nhau có ghi rõ trong phần tài liệu tham
khảo.
Ngoài ra, trong đồ án còn sử dụng một số nhận xét, đánh giá cũng như số liệu
của các tác giả khác, cơ quan tổ chức khác đều có trích dẫn và chú thích nguồn gốc.
Nếu phát hiện có bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách
nhiệm về nội dung đồ án của mình. Trường đại học Tôn Đức Thắng không liên
quan đến những vi phạm tác quyền, bản quyền do tôi gây ra trong quá trình thực
hiện (nếu có).
TP. Hồ Chí Minh, ngày tháng năm
Tác giả
(ký tên và ghi rõ họ tên)
Nguyễn Quốc Thái
Lưu Quang Thắng
5
- PHẦN XÁC NHẬN VÀ ĐÁNH GIÁ CỦA GIẢNG VIÊN
Phần xác nhận của GV hướng dẫn
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
Tp. Hồ Chí Minh, ngày tháng năm
(kí và ghi họ tên)
Phần đánh giá của GV chấm bài
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
6
- Tp. Hồ Chí Minh, ngày tháng năm
(kí và ghi họ tên)
7
- TÓM TẮT
Xây dựng câu đố Sudoku sử dụng Latin Squares
8
- MỤC LỤC
9
- DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT
10
- DANH MỤC CÁC BẢNG BIỂU, HÌNH VẼ, ĐỒ THỊ
DANH MỤC HÌNH
11
- CHƯƠNG 1 – MÔ TẢ BÀI TOÁN
Sudoku là bảng câu đó 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à manh mối để tìm lời
giải. Tùy theo mức độ nhiều hay ít của manh mối, các câu đố được xếp theo loại
dễ, trung bình, khó
Mục tiêu của Câu đố Sudoku là điền các chữ số vào một lưới 9×9 sao cho mỗi cột,
mỗi hàng, và mỗi phần trong số chín lưới con 3×3 cấu tạo nên lưới chính (cũng gọi
là "hộp", "khối", hoặc "vùng") đều chứa tất cả các chữ số từ 1 tới 9. Câu đố đã
được hoàn thành một phần, người chơi phải giải tiếp bằng việc điền số sao cho:
+ Các số cùng 1 dòng không được trùng
+ Các số cùng 1 cột không được trùng
+ Các số trong cùng 1 ô 3x3 không được trùng
+ Thứ tự điền số là không quan trọng
12
- CHƯƠNG 2 – CÁC BƯỚC GIẢI BÀI TOÁN
Bước 1: Tạo ra 1 Latin Squares 3x3 gồm 3 số 0, 1 và 2
Một hình vuông Latin là một mảng n × n sao cho các số xuất hiện trong một
hàng không được trùng nhau và các số xuất hiện trong 1 cột không được trùng nhau
Latin Squares 3x3 sau khi tạo
Bước 2: Tạo ra thêm Latin Squares 3x3 gồm 3 số 0, 1 và 2 ứng
với mỗi một số trong Latin Squares vừa tạo ở bước 1
Các Latin Squares 3x3 vừa tạo ở bước này không được trùng nhau
Bước 3: Chuyển các số từ hệ 3 sang hệ 10
Coi các số 0,1,2 là các số hệ 3 và sẽ chuyển nó sang hệ 10
13
- Xét trong 1 ô Latin Squares 3x3 chúng ta sẽ chuyển nó sang hệ 10 như sau
Mỗi ô của Latin Squares tạo ở bước 2 sẽ được gán với số tương ứng của ô Latin
Squares vừa tạo ở bước thứ 1
Công thức: Số được gán vào ô Latin Squares x 3 + số đang xét + 1
Dòng thứ 1:
2×3+0+1=7
2×3+2+1=9
2×3+1+1=8
Dòng thứ 2:
2×3+1+1=8
2×3+0+1=7
2×3+2+1=9
Dòng thứ 3:
2×3+2+1=9
2×3+1+1=8
14
- 2×3+0+1=7
Cuối cùng chúng ta có kết quả như sau:
Bước 4: Chuyển các dòng với nhau để các số trong cùng 1 ô 3x3
không bị trùng
Sau khi làm xong 3 bước trên chúng ta sẽ có 1 bảng như sau:
Chuyển dòng 2 và dòng 4 cho nhau
Chuyển dòng 3 và dòng 7 cho nhau
Chuyển dòng 6 và dòng 8 cho nhau
15
- Chúng ta sẽ được:
Bước 5: Đục lỗ
Số lỗ sẽ do người chơi đưa ra
Số lỗ phải là bội của 9 và được chia đều cho các ô 3x3
Ví dụ:
Người chơi cho số lỗ là 54 lỗ
Có 9 ô 3x3 thì số lỗ của mỗi ô là 6
16
- 17
- CHƯƠNG 3 – CODE
Bước 1: Tạo ra 1 Latin Squares 3x3 gồm 3 số 0, 1 và 2
Bước 2: Tạo ra thêm Latin Squares 3x3 gồm 3 số 0, 1 và 2 ứng
với mỗi một số trong Latin Squares vừa tạo ở bước 1
18
- Bước 3: Chuyển các số từ hệ 3 sang hệ 10
Bước 4: Chuyển các dòng với nhau để các số trong cùng 1 ô 3x3
không bị trùng
Bước 5: Đục lỗ
19
- 20
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
