Lab 2 - CSC14003 - Hashiwokakero

Repo này là một phần của đồ án 2 môn học CSC14003 - Cơ sở trí tuệ nhân tạo (HCMUS).

1. Giới thiệu

Repo này chứa mã nguồn cài đặt các phương pháp để giải bài toán logic Hashiwokakero: PySAT, A*, Backtracking, Brute-force.

Ngoài ra, repo đồng thời cung cấp:

• Bộ CLI thống nhất để chạy thí nghiệm từ command line.
• Hệ thống chạy toàn bộ thực nghiệm và trực quan hóa các kết quả.

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

├── core/
│   ├── encoder.py                 # Encoder mã hóa grid thành CNF
│   ├── decoder.py                 # Decoder giải mã mô hình thành lời giải
│   ├── basesolver.py              # Lớp cha cho tất cả solvers
│   ├── solver_pysat.py            # Solver sử dụng thư viện PySAT
│   ├── solver_astar.py            # Solver sử dụng thuật toán A*
│   ├── solver_backtracking.py     # Solver sử dụng thuật toán Backtracking
│   └── solver_bruteforce.py       # Solver sử dụng thuật toán Brute-force
│
├── experiments/
│   ├── configs.py                 # Cấu hình các thông số, solvers... chạy benchmark
│   ├── benchmark.py               # Thực nghiệm trên các chỉ số tốc độ, dung lượng...
│   └── visualization.py           # Trực quan hóa kết quả thực nghiệm
│
├── inputs/                        # Inputs mẫu ma trận kích thước từ 3x3 đến 20x20
├── outputs/                       # Chứa kết quả chạy thực nghiệm, thư mục chứa kết quả mặc định
├── utils/                         # Định nghĩa kiểu dữ liệu mới
│
├── helper.py                      # Các hàm hỗ trợ việc giải toán
├── main.py                        # Chương trình chính
├── requirements.txt               # Danh sách thư viện Python cần cài đặt
└── README.md                      # Tài liệu hướng dẫn sử dụng

3. Cài đặt môi trường

3.1 Yêu cầu môi trường

Trong đồ án này, nhóm sử dụng Pseudo-Boolean (PB) encoding thông qua thư viện pypblib nhằm tối ưu tốc độ sinh mệnh đề CNF từ ma trận đầu vào. Thư viện này phụ thuộc vào mã nguồn C++ và không tương thích với trình biên dịch MSVC trên Windows, do đó không thể chạy trực tiếp trên Windows thuần.

Vì lý do trên, chương trình yêu cầu môi trường Linux/Ubuntu WSL để biên dịch và chạy đúng.

Các lệnh hướng dẫn ở các phần sau sẽ được điều chỉnh để chạy phù hợp trên môi trường Linux/Ubuntu WSL.

3.2. Clone repository

git clone https://github.com/dwctien/ai-lab2-hashiwokakero.git
cd ai-lab2-hashiwokakero

3.3. Tạo môi trường ảo

python3 -m venv venv
source venv\Scripts\activate

3.4. Cài đặt thư viện

pip3 install -r requirements.txt

4. Sử dụng

Để thực hiện giải bài toán Hashiwokakero bằng các solver, tiến hành nhập lệnh sau:

python3 main.py --solver SOLVER --input INPUT [--output OUTPUT]

Ý nghĩa của các lựa chọn như sau:

Option	Mục đích	Giá trị
SOLVER	Chọn phương pháp giải toán	PySAT, AStar, Backtracking, Bruteforce	Bắt buộc
INPUT	Chọn testcase mẫu	input-01.txt ... input-15.txt	Bắt buộc
OUTPUT	Đường dẫn thư mục chứa kết quả		Không bắt buộc

Để xem hướng dẫn sử dụng chi tiết, nhập:

python3 main.py --help

Để chạy toàn bộ thực nghiệm, nhập lệnh sau:

python3 -m experiments.benchmark

Dưới đây là một số ví dụ sử dụng:

• Giải bài toán trong file input-06.txt bằng thư viện PySAT

python3 main.py --solver pysat --input input-06.txt

• Giải bài toán trong file input-14.txt bằng thuật toán Brute-force

python3 main.py --solver bruteforce --input input-14.txt