1. Giới thiệu#

Slitherlink là một câu đố logic với luật chơi như sau:

• Nối các điểm trên một lưới theo phương ngang hoặc dọc để tạo thành một chu trình khép kín, không chồng chéo, rẽ nhánh
• Một số ô được tạo thành từ 4 điểm trong lưới được điền sẵn một số nhỏ hơn 4 thể hiện số đường cần bao quanh ô đó (các ô trống có thể có số đường bao quanh tùy ý)

Chú ý: một đường được định nghĩa là một kết nối giữa 2 điểm kề nhau

Dưới đây là ví dụ cho một câu đố Slitherlink cỡ 7×7 và lời giải

2. Mô hình hóa câu đố#

• $n_R$ là số hàng của lưới
• $n_C$ là số cột của lưới
• $F$: Tập hợp các ô có số bên trong
• $L(i, j)$: Số được điền bên trong ô $(i, j)$
• $N_H(i, j)$: Các đường ngang nối với điểm $(i, j)$
• $N_V(i, j)$: Các đường dọc nối với điểm $(i, j)$

2.1. Biến quyết định#

Để giải quyết bài toán này ta cần đặt biến cho mỗi đường trên lới và mỗi điểm trên lưới. Cụ thể như sau

• Với mỗi đường nằm ngang $(i, j)$ trong lưới ($0 \leq i < n_R + 1, 0 \leq j < n_C$), xây dựng biến $h(i, j)$ thỏa mãn

• Với mỗi đường nằm dọc $(i, j)$ trong lưới ($0 \leq i < n_R, 0 \leq j < n_C + 1$), xây dựng biến $v(i, j)$ thỏa mãn

• Với mỗi điểm $(i, j)$ trong lưới ($0 \leq i < n_R + 1, 0 \leq j < n_C + 1$), xây dựng biến $p(i, j)$ thỏa mãn

2.2. Các ràng buộc#

• Số đường bao quanh một ô bằng số được điền trong ô đó (ngoại trừ các ô để trống)

• Các điểm phải nối với nhau thành một chu trình khép kín, không chồng chéo, rẽ nhánh.

  Để mô hình hóa điều kiện này một cách trực tiếp là một điều không hề dễ dàng, vì vậy ở đây ta sẽ mô hình hóa một phần của điều kiện và sử dụng một thuật toán được nêu ở mục 2.4 để giải quyết bài toán. Cụ thể, ta mô hình hóa điều kiện: "Các điểm phải nối với nhau thành một số chu trình tách rời, khép kín, không chồng chéo, rẽ nhánh".

2.3. Hàm mục tiêu#

Bài toán này không có hàm mục tiêu, bởi vì ta không cần tối thiểu hóa hay tối đa hóa gì cả, việc cần làm chỉ là tìm ra một nghiệm chấp nhận được. Về mặt kỹ thuật, khi lập trình ta có thể để hàm mục tiêu là một hằng số (mình hay chọn số 0).

2.4. Triển khai bài toán#

Khi giải mô hình trên, ta thu được một lời giải đã thỏa mãn hầu hết các điều kiện của bài toán trừ việc thay vì ta muốn có một chu trình duy nhất thì ta có thể có thêm nhiều chu trình tách rời khác. Để giải quyết vấn đề này ta sử dụng thuật toán sau:

BEGIN Slitherlink
    khởi tạo mô hình M;
    giải M;
    S := nghiệm của M;
    WHILE (S còn chứa nhiều hơn 1 chu trình)
        thêm các điều kiện để cắt tất cả chu trình trong S;
        giải M;
        S := nghiệm của M;
    END
    Return S;
END

Với điều kiện dùng để cắt chu trình được mô hình hóa như sau

Trong đó, $C$ là tập hợp tất cả các chu trình thu được sau một lần giải, $H_c$ là tập hợp tất cả các đường ngang trong chu trình $c$, $V_c$ là tập hợp tất cả các đường dọc trong chu trình $c$.

3. Kết luận#

Điểm nhấn của câu đố này nằm ở thuật toán dùng để cắt chu trình, đây là một ý tưởng rất thú vị khi gặp các bài toán khó mô hình, ta có thể giải nhiều mô hình xấp xỉ cho đến khi tìm được lời giải đúng

Tham khảo thêm các câu đố Slitherlink và biến thể tại Krazydad. Code mô hình hóa Slitherlink bằng python có tại Tung-hehe.

Happy modeling!