Các tập hợp gần như bị chặn
Các tập hợp gần như bị chặn
Các kỹ thuật liên quan
Tập hợp gần như bị khóa là gì?
Một ALS là N ô trong một nhà duy nhất với đúng N+1 ứng viên khác nhau. Nó là "gần như bị khóa" -- loại bỏ một ứng viên thì nó trở thành một tập hợp trần. ALS đơn giản nhất là một ô hai giá trị Ô (1 Ô, 2 ứng viên). Tất cả các ô phải chia sẻ một nhà.
Thế nào là một ứng viên chung bị giới hạn?
RCC là một chữ số xuất hiện cả trong ALS A và ALS B, sao cho mọi trường hợp của chữ số này trong A đều nhìn thấy mọi trường hợp của chữ số này trong B. Vì hai tập ALS không thể cùng sử dụng RCC tại cùng một thời điểm, nên ít nhất một trong hai tập ALS phải mất RCC và trở thành một tập khóa.
Áp lực tạo thành tập khóa này là lý do tạo ra các loại bỏ. Nếu hai tập ALS cũng chia sẻ thêm một chữ số Z khác, thì Z phải xuất hiện trong ít nhất một trong hai tập ALS. Bất kỳ Ô bên ngoài nào mà nhìn thấy tất cả các vị trí có thể của Z trong cả hai tập ALS đều không thể chứa Z.
ALS-XZ: Quy tắc Hai ALS Chính
ALS-XZ sử dụng hai tập hợp con (ALS). Chúng chia sẻ một ứng cử viên chung bị hạn chế X và một ứng cử viên chung thứ hai Z. Vì X không thể xuất hiện đồng thời ở cả hai ALS, nên ít nhất một ALS phải được giải mà không có X. Khi điều đó xảy ra, Z sẽ bị khóa vào ALS đó, trừ khi Z đã bị buộc phải xuất hiện ở ALS kia.
Do đó, Z phải xuất hiện ở đâu đó trong hai ALS. Loại bỏ Z khỏi bất kỳ Ô nào nhìn thấy tất cả các ứng cử viên Z trong cả hai ALS. Cấp độ 10 (Chuyên gia).
Các tập hợp gần như bị chặn: Tìm kiếm ALS
Ứng dụng cũng liệt kê Các tập hợp gần như bị chặn như một kỹ thuật vì nhận biết được ALS là hữu ích ngay cả khi riêng lẻ. Một ALS không phải là một phép loại trừ cho đến khi nó tương tác với một ALS khác, một nút giao Ô, hoặc một giao điểm giữa khối và dòng. Kỹ năng thực tế là học cách nhận ra các nhóm nhỏ các ô mà hợp của các ứng cử viên chỉ lớn hơn một chữ số so với số lượng ô.
Hầu hết các kỹ thuật dựa trên ALS bắt đầu bằng việc phân loại các tập hợp này, sau đó kiểm tra xem các ứng cử viên chung có khả năng nhìn thấy nhau hay không để thực hiện một RCC.
Chuỗi ALS: Kết nối nhiều Các tập hợp gần như bị chặn
Một Chuỗi ALS nối kết nhiều tập hợp ALS qua các RCC. Mỗi cặp kề nhau có một ứng cử viên chung bị giới hạn, và chuỗi này luân phiên xác định tập hợp ALS nào bị buộc phải trở thành tập hợp khóa khi xét từng RCC.
Điểm loại bỏ xuất hiện trong cả tập hợp ALS đầu và cuối chuỗi. Nếu một Ô bên ngoài nhìn thấy tất cả các vị trí khả dĩ của mục tiêu ở cả hai đầu chuỗi, nó có thể bị loại bỏ. Cấp độ 11 (Cực kỳ). ALS-XZ là phiên bản ngắn nhất có ích của ý tưởng này.
Sue de Coq: Mẫu giao nhau ALS
Sue de Coq khai thác giao điểm giữa một khối với một hàng hoặc cột. Giao điểm này chứa hai hoặc ba ô thuộc cả hai khu vực. Các ứng viên trong các ô giao điểm này phải đến từ phía hàng, phía khối, hoặc chính phần giao nhau.
Kỹ thuật này tìm hai tập hợp hỗ trợ: một ở phần còn lại của hàng hoặc cột, và một ở phần còn lại của khối. Các ứng viên của chúng không giao nhau, và cùng nhau chúng giải thích toàn bộ các ứng viên có thể nằm trong phần giao nhau. Sau khi hoàn tất việc kiểm tra, các ứng viên trùng khớp có thể bị loại bỏ khỏi các ô khác trong cùng hàng hoặc khối.
Cấp độ 9 (Chuyên gia).
Hoa chết: Kỹ thuật ALS Thân và Nhị hoa
Hoa chết bắt đầu bằng một nhánh Ô có N ứng viên. Đối với mỗi ứng viên nhánh, có một tập hợp ALS lá hoa tương ứng. Nếu nhánh chọn một ứng viên, thì tập hợp lá hoa tương ứng sẽ mất ứng viên đó và trở thành bị khóa.
Dù nhánh cuối cùng chọn giá trị nào, thì một trong các lá hoa sẽ bị buộc vào trạng thái khóa. Nếu chữ số loại bỏ xuất hiện trên tất cả các lá hoa, thì chữ số đó phải được cung cấp bởi ít nhất một lá hoa. Bất kỳ ô Ô nào bên ngoài mà nhìn thấy mọi trường hợp có thể của chữ số đó trên các lá hoa đều có thể loại bỏ nó.
Cấp độ 11 (Cực kỳ).
Làm thế nào để tìm mẫu ALS
Danh sách các ALS trong mỗi nhà. Tìm các cặp chia sẻ ứng viên với các RCC hợp lệ. Đối với Sue de Coq, hãy tập trung vào các giao điểm khối-dòng. Đối với Hoa chết, hãy bắt đầu từ các tế bào gốc có ít ứng viên.
Đánh giá độ khó
Các tập hợp gần như bị chặn: Cấp độ 9, Chuyên gia
Sue de Coq: Cấp độ 9, Chuyên gia
ALS-XZ: Cấp độ 10, Chuyên gia
Chuỗi ALS: Cấp độ 11, Cực độ
Hoa chết: Cấp độ 11, Cực độ
Tóm tắt
Các kỹ thuật ALS dựa trên hai khái niệm: tập hợp gần như khóa (N ô, N+1 giá trị khả dĩ) và ứng viên chung bị giới hạn. Các tập hợp gần như bị chặn cung cấp các khối xây dựng; ALS-XZ, chuỗi ALS, Sue de Coq, và Hoa chết sử dụng những khối này theo các cấu hình khác nhau. Cùng nhau, chúng tạo thành một trong những họ kỹ thuật mạnh nhất để giải các bài toán khó nhất.
Các kỹ thuật liên quan