Ép buộc

Ép buộc

Bậc thầy

Đây có phải là đoán không? Tranh cãi về Chuỗi ép buộc

Chuỗi ép buộc không phải là đoán khi được dùng như một kỹ thuật chứng minh. Bạn tạm thời xét mọi nhánh từ một điểm xuất phát đã chọn, lan truyền logic từng nhánh và chỉ giữ lại những kết luận mà mọi nhánh đều ủng hộ hoặc những kết luận bị ép buộc bởi mâu thuẫn.

Khác biệt then chốt so với đoán là sự cam kết. Một phỏng đoán chọn một nhánh và tiếp tục như thể nó đúng. Một chuỗi cưỡng bức so sánh tất cả các nhánh liên quan từ điểm xuất phát và chỉ hành động khi sự so sánh chứng minh được điều gì đó.

Chuỗi ép buộc kém thanh lịch hơn các kỹ thuật dựa trên mẫu, nhưng kết luận của chúng được chứng minh là đúng khi mọi nhánh đã được kiểm tra chính xác.

Ô chuỗi cưỡng bức

Bắt đầu từ một ô hai giá trị {A, B}. Lan truyền các hệ quả cho từng nhánh. So sánh kết quả.

Mâu thuẫn: một nhánh không hợp lệ, nên ô phải là ứng viên còn lại.

Hội tụ về vị trí: cả hai nhánh đều cưỡng bức cùng một chữ số vào cùng một ô ở xa.

Hội tụ về loại trừ: cả hai nhánh đều loại trừ cùng một ứng viên khỏi cùng một ô.

Chuỗi cưỡng bức theo vùng (chuỗi cưỡng bức theo chữ số)

Bắt đầu từ 2-3 vị trí của một chữ số trong một nhà. Khám phá từng vị trí như một nhánh. Cùng ba kiểu suy luận.

Cưỡng bức Ô hiệu quả khi các ô hai giá trị có hệ quả vươn xa. Cưỡng bức theo vùng hiệu quả khi vị trí của một chữ số có hiệu ứng lan tỏa mạnh.

Mạng cưỡng bức: mở rộng số nhánh

Ô mạng cưỡng bức: các ô có 3-6 ứng viên. Mạng cưỡng bức theo vùng: các nhà có 4-6 vị trí cho một chữ số. Nhiều nhánh hơn, tốn kém hơn, nhưng có thể tìm ra những suy luận mà Chuỗi ép buộc không thể.

Logic hoàn toàn giống nhau. Chỉ số nhánh khác nhau.

Cỗ máy lan truyền

Mỗi nhánh lan truyền qua các ô đơn trần, ô đơn ẩn, các ứng viên bị khóa và các cặp trần, lặp đi lặp lại cho đến khi ổn định. Một giả định duy nhất có thể lan qua hàng chục bước trung gian khắp toàn bộ bàn cờ.

Khi hai nhánh đi đến cùng một kết luận qua những con đường hoàn toàn khác nhau, sự hội tụ chứng minh kết luận đó một cách chắc chắn.

Ba kiểu suy luận

Mâu thuẫn: một nhánh dẫn đến trạng thái không hợp lệ. Giả định đó là sai. Loại phổ biến nhất.

Hội tụ về vị trí: mọi nhánh đều buộc cùng một chữ số vào cùng một ô. Ít gặp hơn nhưng mang tính quyết định.

Hội tụ về loại bỏ: mọi nhánh đều loại bỏ cùng một ứng viên khỏi cùng một ô. Loại tinh tế nhất.

Khi nào dùng kỹ thuật ép buộc

Phương án logic cuối cùng. Được áp dụng sau khi các kỹ thuật dựa trên mẫu và những chuỗi gọn gàng hơn thất bại.

Chuỗi ép buộc với 2-3 nhánh được thử trước. Lưới ép buộc với 3-6 nhánh tốn kém hơn và thường để dành cho về sau. Cả hai đều ở Cấp 12 (Cực khó).

Đối với trình giải bằng máy tính, ép buộc có giới hạn là một cỗ máy chứng minh mạnh mẽ nhưng không tự động đầy đủ. Tính đầy đủ chỉ đến khi cho phép tìm kiếm mở rộng đủ xa để bao quát các giả định cần thiết, điều này tiệm cận với việc quay lui vét cạn. Trên thực tế, ép buộc được mô tả đúng nhất như một cuộc tìm kiếm logic có kiểm soát hơn là sự bảo đảm rằng bất kỳ trình giải có độ sâu cố định nào cũng giải được mọi câu đố hợp lệ.

Một ghi chú triết học về tính thanh thoát và tính đầy đủ

Các kỹ thuật dựa trên mẫu bộc lộ những mối quan hệ cấu trúc và thanh thoát hơn. Nhưng tồn tại những câu đố hợp lệ đòi hỏi logic ở mức ép buộc. Kỹ thuật ép buộc là tấm lưới an toàn bắt được mọi câu đố mà kỹ thuật dựa trên mẫu không xử lý được.

Cách tiếp cận thỏa mãn nhất: thử mọi kỹ thuật dựa trên mẫu trước, rồi chỉ viện đến ép buộc khi câu đố thực sự đòi hỏi.

Tóm tắt

Chuỗi ép buộc và lưới ép buộc nằm trong số những kỹ thuật logic mạnh mẽ nhất, ở Cấp 12 (Cực khó). Chúng khám phá mọi nhánh từ một điểm xuất phát đã chọn, lan truyền hệ quả và so sánh kết quả. Các suy luận đến qua mâu thuẫn, hội tụ về vị trí hoặc hội tụ về loại bỏ. Chúng là phương án cuối cùng trước khi quay lui vét cạn; nếu mở rộng không giới hạn thực tế, chúng trở thành một chứng minh tìm kiếm đầy đủ, nhưng ép buộc kiểu con người có giới hạn vẫn là một kỹ thuật nâng cao có mục tiêu.