Vì sao cần vét cạn có định hướng

Giới hạn kích thước tile khiến chỉ có 35 tile phân biệt, do đó “chỉ” có \(35\cdot34/2=595\) cặp. Ta có thể loại vài cặp bằng nhận xét riêng: chẳng hạn tile 9 ô và tile 8 ô chắc chắn không thể dùng chung vì bội chung nhỏ nhất của 9 và 8 là 72, lớn hơn 64 ô bảng. Ta thậm chí có thể cắt tile giấy để thử bằng tay, nhưng sẽ nhanh chóng thấy việc này khó hơn tưởng tượng, nhất là chứng minh một trường hợp là bất khả thi. Hoặc phải viết cả một luận văn về các \(n\)-omino, hoặc phải dùng vét cạn.

Không thể liệt kê độc lập mọi cách lát một phần hay toàn bộ bảng bằng từng loại rồi lấy giao: riêng tile \(1\times1\) đã có \(2^{64}\) tập ô có thể lát. Dù xử lý riêng được vài tile nhỏ, ta vẫn phí thời gian sinh vô số tập hiển nhiên không tương thích với tile kia.

Thay vào đó, dùng quay lui tận dụng ràng buộc, để cách đặt một loại tile dẫn đường cho loại còn lại. Thuật toán không cần nhanh chớp nhoáng: vì biết cả 595 trường hợp đều có trong test, có thể sinh lời giải cho tất cả ngoại tuyến rồi nộp một lần; nhưng vẫn phải sinh xong trước khi Chung kết thế giới kết thúc.

Tiền xử lý mọi vị trí đặt

Đánh số 64 ô theo thứ tự hàng trước, cũng là thứ tự tìm kiếm. Với mỗi tile, sinh tất cả phép quay và phản xạ, rồi tịnh tiến chúng trên bảng để có mọi vị trí đặt hợp lệ. Gán mỗi vị trí đặt cho ô có số nhỏ nhất mà nó phủ. Ví dụ, một hình vuông \(2\times2\) có thể phủ các ô 1, 2, 9, 10; ta chỉ gán vị trí đó cho ô 1. Liệt kê lại dưới ô 10 là thừa, vì đến lúc tìm kiếm tới ô 10, vị trí ấy đã được cân nhắc tại ô 1.

Quay lui đồng thời hai phép lát

Bắt đầu từ góc trên trái và duyệt theo hàng. Tại mỗi ô \(c\), quyết định có đưa nó vào tập đỏ không. Nếu ô đã bị một tile đặt trước phủ thì bắt buộc phải tô. Nếu quyết định tô mà một hoặc cả hai phía chưa phủ ô đó, thử tất cả vị trí đặt của loại tile tương ứng đã được gán cho \(c\), miễn là không chồng lên tile đã đặt cùng phía.

Vì bảng có \(8\times8\) ô, có thể biểu diễn vùng phủ của mỗi phía bằng các bit của số 64 bit. Phép toán bit giúp kiểm tra giao, thêm một tile và so sánh hai trạng thái rất nhanh. Ngay khi hai mask bằng nhau và khác 0, dừng, lần theo các lựa chọn quay lui để phân hoạch tập đó thành tile ở mỗi phía, rồi in hai phép lát. Nếu toàn bộ cây tìm kiếm kết thúc mà không gặp trạng thái như vậy thì trường hợp là IMPOSSIBLE.

Không có cận đa thức cho phép quay lui này, nhưng thực tế toàn bộ trường hợp chạy trong vài giây. Tile nhỏ “linh hoạt”, nên các cặp chứa chúng thường tìm được nghiệm rất sớm: cây đệ quy rộng nhưng nông. Tile lớn nhanh chóng lấp đầy bảng và không tạo nhiều lựa chọn: cây cao nhưng hẹp.

Phương pháp không nhất thiết tìm tập ô nhỏ nhất, nhưng có thể tạo ra những hình và phép lát đẹp mắt, thậm chí là câu đố thực sự thú vị. Phân tích chính thức minh họa một nghiệm dạng “mắt xích” do các tile góc cạnh tạo nên, với sự pha trộn bất ngờ giữa vùng đặc và vùng nhiều lỗ. Một minh họa khác chơi chữ bằng các tile gần giống hình trái tim: hy vọng bạn đã “loved” bài này. Chi tiết cuối cũng nhắc rằng hai tile chỉ khác nhau rất ít không nhất thiết làm test dễ hơn.

Dựa trên phân tích chính thức của Google Code Jam 2018, Chung kết thế giới, bài Two-Tiling.