Kakuro Puzzle Optimization

Dự án môn Tối ưu hóa (Optimization). Dự án này tập trung vào việc mô hình hóa bài toán giải đố logic Kakuro dưới dạng một bài toán Quy hoạch tuyến tính nguyên hỗn hợp (MILP - Mixed Integer Linear Programming) và sử dụng bộ giải Gurobi để tìm nghiệm chính xác.

1. Thông tin

Trường Đại học Khoa học Tự nhiên, ĐHQGHN - Khoa Toán - Cơ - Tin học

Thành viên	MSSV	Lớp
Đinh Bảo Triết (Leader)	23000164	K68A2 Toán Tin
Đỗ Minh Hoàng	23000121	K68A2 Toán Tin
Ninh Trung Kiên	23000130	K68A2 Toán Tin

2. Giới thiệu bài toán Kakuro

Kakuro là một trò chơi logic số học trên lưới ô vuông, trong đó:

• Ô trắng: Cần điền các số từ 1 đến 9.
• Ô gợi ý: Chứa tổng mục tiêu của một hàng hoặc một cột liền kề.
• Luật chơi: Tổng các số điền vào phải bằng giá trị gợi ý và không có số nào lặp lại trong cùng một nhóm tổng.

Thay vì giải bằng thuật toán quay lui (Backtracking) truyền thống, dự án này tiếp cận dưới góc độ Mô hình hóa Toán học (Mathematical Modeling), chuyển đổi các luật chơi thành các phương trình và bất phương trình tuyến tính. Đây là một bài toán khả thi (Feasibility Problem) không có hàm mục tiêu.

3. Cấu trúc thư mục

Kakuro-Puzzle-Optimization/
├── data/                   # Các file đề bài Kakuro kích thước lớn và ảnh mẫu
├── docs/                   # Slide báo cáo dự án (.pdf)
├── result/                 # Các hình ảnh kết quả giải đố đã kết xuất (.png)
├── source.py               # Mã nguồn chính: Xây dựng mô hình MILP và giao diện
└── README.md               # Tài liệu hướng dẫn dự án

4. Mô hình Toán học (MILP Model)

Mô hình sử dụng biến quyết định nhị phân $x_{i,j,k} \in {0, 1}$ (bằng 1 nếu ô trắng $(i,j)$ điền số $k$, ngược lại bằng 0).

Hệ thống ràng buộc cốt lõi (Constraints):

1. Ràng buộc điền số: Mỗi ô trắng chứa đúng một số từ 1 đến 9.

$$\sum_{k=1}^{9} x_{i,j,k} = 1 \quad \forall (i,j) \in W$$

2. Ràng buộc tổng: Tổng các giá trị trong một nhóm $G$ bằng đúng giá trị gợi ý $T_G$.

$$\sum_{(i,j) \in G} \sum_{k=1}^{9} k \cdot x_{i,j,k} = T_G \quad \forall G \in C$$

3. Ràng buộc duy nhất: Không có số nào xuất hiện quá 1 lần trong cùng một nhóm.

$$\sum_{(i,j) \in G} x_{i,j,k} \le 1 \quad \forall G \in C, \forall k \in {1..9}$$

5. Kết quả thực nghiệm

Mô hình giải quyết cực kỳ hiệu quả với bộ giải Gurobi. Thuật toán tự động tìm ra nghiệm tối ưu (Optimal) ngay cả với các bảng kích thước rất lớn.

Câu đố Kakuro (Input)

Kết quả giải (Output)

(Ảnh bảng Kakuro mẫu và kết quả giải đố được tự động vẽ bằng thư viện Matplotlib)

6. Cài đặt và Thực thi

Môi trường và Thư viện

Bạn cần cài đặt các thư viện sau:

pip install gurobipy matplotlib

Lấy giấy phép bản quyền Gurobi (Academic License)

Vì Gurobi là một bộ giải thương mại mạnh mẽ, mã nguồn này yêu cầu phải có giấy phép (License) hợp lệ để chạy:

1. Truy cập Trang chủ Gurobi và tạo một tài khoản bằng email trường đại học (@hus.edu.vn).
2. Vào mục Academic License, xin cấp một giấy phép miễn phí.
3. Copy đoạn mã kích hoạt (có dạng grbgetkey xxxxxxxx-...).
4. Mở Terminal (Command Prompt) trên máy tính, dán lệnh đó vào và nhấn Enter để cài đặt giấy phép.

Thực thi chương trình

Chạy trực tiếp file mã nguồn để xem Gurobi tối ưu hóa và xuất kết quả:

python source.py

7. Tài liệu tham khảo

• H. Simonis, Kakuro as a Constraint Problem, ResearchGate, 2008.
• Tài liệu học tập môn Tối ưu hóa - Trường Đại học Khoa học Tự nhiên, ĐHQGHN.