Trò chơi – Giả sử mảng n×n ô vuông. Một số ô trống, một số đặc (solid), một số ô không đặc được gán số nguyên 1,2,3... Mỗi số chiếm đúng 2 ô khác nhau. Người chơi nối 2 lần xuất hiện của mỗi số bằng đường đơn giản chỉ dùng di chuyển ngang/dọc. Hai đường khác nhau không được cắt nhau. Đường không được đi qua ô đặc. Cuối cùng tất cả ô không đặc phải được lấp đầy bởi các đường.
Thuật toán – Tạo puzzle ngẫu nhiên hợp lệ kích thước n×n: trước sinh các đường đơn giản ngẫu nhiên không cắt nhau trên bàn cờ. Nếu còn ô đơn lẻ ngoài các đường, đánh dấu chúng là solid (cấm). Cung cấp đầu mút các đường và danh sách ô đặc làm puzzle.
Do đó trước sinh lời giải (solution), sau ra puzzle từ lời giải. Các đường và ô đặc phân hoạch bàn cờ n×n. Dùng cấu trúc dữ liệu union-find sinh phân hoạch này. Cấu trúc xử lý các tập con của tập n² ô trên bàn cờ.
Giả mã (PseudoCode)
- Tìm ô (a,b) và (c,d) ngẫu nhiên trên bàn cờ sao cho:
- (a,b) và (c,d) là hàng xóm, và
- không ô nào thuộc đường đã sinh. Nếu không tìm thấy cặp nào, trả về FAILURE. (Ở đây (a,b) và (c,d) là hai ô đầu của đường mới.)
- Hợp nhất (union) hai cây union-find chứa (a,b) và (c,d).
- Lặp cho đến khi đường hiện tại không thể mở rộng:
- Đổi tên (a,b) = (c,d).
- Tìm ô hàng xóm ngẫu nhiên (c,d) của (a,b) sao cho:
- (c,d) không thuộc đường đã sinh (kể cả đường hiện tại)
- chỉ (a,b) là hàng xóm của (c,d) trên đường đang xây một phần.
- Nếu không tìm thấy (c,d) -> đường không mở rộng thêm, thoát vòng lặp.
- Ngược lại, hợp nhất hai cây union-find chứa (a,b) và (c,d).
- Đặt cờ endpoint cho hai ô ở đầu và cuối đường mới.
- Trả về SUCCESS.