Thực hiện ép buộc

Có phải là đoán mò? Vấn đề Chuỗi ép buộc

Số Chuỗi ép buộc khai thác mọi khả năng đồng thời mà không cam kết vào bất kỳ giả định nào. Chúng so sánh tất cả các nhánh và chỉ hành động khi các nhánh hội tụ. Ba đặc điểm nổi bật: khai thác toàn diện, kết luận xác định và tính đúng đắn có thể chứng minh. 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 được chứng minh là đúng đắn.

Ô Chuỗi ép buộc

Bắt đầu từ một ô có hai giá trị khả dĩ Ô {A, B}. Tiến hành suy luận theo từng nhánh. So sánh kết quả. Mâu thuẫn: một nhánh bị vô hiệu, do đó Ô phải là giá trị còn lại. Hội tụ tại vị trí: cả hai nhánh đều buộc cùng một chữ số vào cùng một ô xa Ô. Hội tụ tại loại bỏ: cả hai nhánh đều loại bỏ cùng một giá trị khỏi cùng một ô Ô.

Chuỗi ép buộc vùng (chuỗi ép buộc 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. Ba loại suy luận giống nhau. Ô ép buộc hiệu quả khi các ô hai giá trị có ảnh hưởng rộng lớn. Ép buộc vùng hiệu quả khi vị trí của một chữ số có tác động dồn dập mạnh mẽ.

Mạng ép buộc: Mở rộng số lượng nhánh

Ô Net ép buộc: các ô có 3-6 lựa chọn. Net ép buộc 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ể phát hiện được các suy luận Chuỗi ép buộc không thể. Lập luận là giống nhau. Chỉ khác nhau ở số lượng nhánh.

Động cơ lan truyền

Mỗi nhánh lan truyền qua các số đơn độc trần, số đơn độc ẩn, Các ứng viên bị khóa, và cặp số trần, lặp lại cho đến khi ổn định. Một giả định đơn lẻ có thể lan truyền qua hàng chục bước trung gian trên toàn bộ bảng. Khi hai nhánh đạt đến cùng một kết luận bằng hai con đường hoàn toàn khác nhau, sự hội tụ này chứng minh kết luận đó là chắc chắn.

Ba loại suy luận

Mâu thuẫn: Một nhánh tạo ra trạng thái không hợp lệ. Giả định đó là sai. Thường gặp nhất. Hội tụ tại vị trí: Tất cả các nhánh đều buộc cùng một chữ số vào cùng một Ô. Ít phổ biến nhưng quyết đoán. Hội tụ tại loại bỏ: Tất cả các nhánh đều loại bỏ cùng một ứng cử viên khỏi cùng một Ô. Dạng tinh tế nhất.

Khi nào nên sử dụng kỹ thuật ép buộc

Lựa chọn cuối cùng về mặt logic. Được áp dụng sau khi tất cả các kỹ thuật khác đều thất bại. Chuỗi ép buộc (2-3 nhánh) được thử trước. Mạng ép buộc (3-6 nhánh) chỉ được dùng khi chuỗi thất bại. Cả hai đều ở cấp độ 12 (Cực độ). Đối với các trình giải máy tính, mạng ép buộc đảm bảo tính toàn vẹn: đảm bảo rằng logic đơn thuần có thể giải được mọi bài toán hợp lệ.

Một ghi chú triết học về sự thanh lịch và tính toàn vẹn

Các kỹ thuật dựa trên mẫu phơi bày các mối quan hệ cấu trúc và mang tính thanh lịch hơn. Tuy nhiên, vẫn tồn tại các bài toán hợp lệ yêu cầu logic cấp độ ép buộc. Các kỹ thuật ép buộc là mạng an toàn, bắt giữ mọi bài toán mà các kỹ thuật dựa trên mẫu không thể xử lý. Cách tiếp cận mang lại sự thỏa mãn nhất: hãy thử mọi kỹ thuật dựa trên mẫu trước, sau đó mới dùng kỹ thuật ép buộc khi bài toán thực sự đòi hỏi.

Tóm tắt

Chuỗi ép buộc và forcing net là những kỹ thuật logic mạnh nhất, ở cấp độ 12 (Cực kỳ). Chúng khám phá mọi khả năng từ một điểm khởi đầu, lan truyền hệ quả và so sánh kết quả. Những suy luận được đưa ra thông qua mâu thuẫn, hội tụ vào vị trí đặt, hoặc hội tụ vào loại bỏ. Đây là phương pháp cuối cùng trước khi dùng phương pháp quét thô, cung cấp tính toàn vẹn cho mọi bài toán Sudoku hợp lệ.