Thạc Sĩ Nghiên cứu và xây dựng một phương pháp đánh giá độ khó cho một Sudoku (9x9)

LỜI MỞ ĐẦU
Từ một trò chơi cổ xuất xứ từ cách đây gần hơn một thiên niên kỷ (990)
và thậm chí có thể cổ hơn nữa, nhân loại đã tìm hiểu và phát hiện vô số các kết
quả toán học quan trọng liên quan đến trò chơi rất đơn giản này: ô số Sudoku.
Sudoku ngày nay đã không đơn thuần là một trò chơi giải trí thường thấy
trên những tờ báo, mà nó còn là đối tượng nghiên cứu quan trọng trong rất nhiều
ngành và lĩnh vực như mã hóa, lý thuyết đồ thị, lý thuyết độ phức tạp, và thậm
chí cả việc phân bố các gene trong sinh học cũng như rất nhiều lĩnh vực khác. Do
vậy, việc tìm hiểu, hệ thống hóa và đề xuất những giải pháp cho các vấn đề về
Sudoku không chỉ nhận được rất nhiều quan tâm của giới học giả hiện nay mà
còn là vấn đề cần thiết và cấp bách cho nhân loại nói chung và những người làm
khoa học nói riêng.
Trong luận văn này, với mong muốn hệ thống hóa và phát triển các vấn đề
cơ bản của Sudoku, chúng tôi xem xét lại bài toán Sudoku tổng quát và cụ thể
hóa các vấn đề kinh điển dưới góc nhìn của toán học, thông qua các khảo sát và
ví dụ ở ô số Sudoku kinh điển, Sudoku bậc 3. Để thực hiện được việc này, chúng
tôi tập trung phân tích chi tiết các vấn đề kinh điển của Sudoku: giải một Sudoku
như thế nào, sinh ra một Sudoku ra sao và làm thế nào lượng giá độ khó của một
Sodoku cho trước. Bên cạnh việc hệ thống hóa các phương pháp tiên tiến hiện
nay, chúng tôi còn đề xuất những phương pháp mới với hiệu quả tốt hơn được
minh chứng qua kết quả thực nghiệm. Trong số những ưu điểm của các phương
pháp này, chúng tôi cho rằng sự kết nối giữa toán học và con người đóng vai trò
rất quan trọng: chúng tôi đã đề xuất được những phương pháp giải quyết các vấn
đề cơ bản của Sudoku hướng đến người chơi (người sử dụng Sudoku) trong đó
vẫn bảo toàn các tính chất của toán học. Chi tiết về những cải tiến này sẽ được
trình bày chi tiết và xuyên suốt trong toàn bộ luận văn.
3
Mục đích nghiên cứu
 Nghiên cứu các kỹ thuật suy luận logic trong quá trình giải một bài toán
Sudoku.
 Nghiên cứu các phương pháp đánh giá độ khó cho một Sudoku và xây
dựng một phương pháp đánh giá độ khó cho một Sudoku cho trước.
 Nghiên cứu các phương pháp sinh Sudoku và tiến hành sinh một Sudoku
theo độ khó cho trước.
1. Đối tượng nghiên cứu
 Bài toán Sudoku 9x9. Các phương pháp suy luận logic phổ biến trong
việc giải bài toán Sudoku (Lone rangers in minigrid, Lone rangers in
column, Triplets in minigrid, Twins in minigrid, ) Các phương pháp
đánh giá độ khó của một Sudoku, các phương pháp sinh Sudoku.
2. Các phương pháp nghiên cứu
Các kết quả thu được từ lý thuyết, thực nghiệm, các kết quả. Cài đặt thuật
toán và chạy trên các phần mềm C# và Maple.
3. Nội dung và phạm vi của vấn đề sẽ đi sâu nghiên cứu
Trong luận văn, việc nghiên cứu và xây dựng một phương pháp đánh giá độ khó cho một Sudoku (9x9) cũng như sinh một Sudoku theo độ khó cho trước
được nghiên cứu sâu hơn.
4. Bố cục luận văn:
Luận văn gồm 4 chương và một phụ lục.
4
Chương 1: Trình bày tổng quan về Sudoku, các hướng nghiên cứu về
Sudoku hiện nay.
Chương 2: Trình bày về các phương pháp suy luận logic cơ bản trong quá
trình giải Sudoku
Chương 3: Là phần trọng tâm của luận văn, trình bày về phương pháp đánh
giá độ khó cho một Sudoku và xây dựng phương pháp đánh giá
độ khó cho một Sudoku. Sinh một Sudoku theo độ khó cho
trước.
Chương 4: Kết luận, đánh giá kết quả đạt được, những hạn chế và hướng
phát triển của đề tài.
Phụ lục : Trình bày thư viện Sudoku, chương trình tính số lần sử dụng
các phương pháp suy luận logic cơ bản trong việc giải một
Sudoku, đánh giá độ khó của Sudoku và sinh một Sudoku theo
độ khó cho trước.

Mục lục
CHƯƠNG 1 TỔNG QUAN VỀ SUDOKU . 6
1. Tổng quan về Sudoku . 6
2. Tình hình nghiên cứu . 10
CHƯƠNG 2 CÁC PHƯƠNG PHÁP SUY LUẬN LOGIC CƠ BẢN . 13
2.1 Column, Row, Minigrid Elimination (CRME) 13
2.2 Lone rangers 16
2.3 Twins . 18
2.4 Triplets . 21
2.5 Brute-force elimination 22
2.6 Backtracking in brute-force elimination . 23
CHƯƠNG 3 SINH SUDOKU . 24
3.1 Đánh giá độ khó cho một Sudoku . 24
3.2 Sinh Sudoku . 30
3.3 THỰC NGHIỆM 34
3.3.1 Đánh giá Sudoku . 34
CHƯƠNG 4 KẾT LUẬN 36
4.1 Các kết quả đạt được 36
4.2 Hạn chế của luận văn : . 36
4.3 Hướng phát triển cho Luận văn : 37
Phụ lục : THƯ VIỆN SUDOKU 38
Tài liệu tham khảo 82