Các tập hợp gần như bị chặn

Các tập hợp gần như bị chặn

Chuyên gia

Tập gần như bị khóa là gì?

ALS là N ô trong một nhà duy nhất với đúng N+1 ứng viên khác nhau. Nó "gần như bị khóa" — bỏ một ứng viên đi thì nó trở thành một tập con trần. ALS đơn giản nhất là một ô hai giá trị (1 ô, 2 ứng viên). Mọi ô phải cùng chung một nhà.

Ứng viên chung bị hạn chế là gì?

RCC là một chữ số xuất hiện trong cả ALS A và ALS B, nơi mọi vị trí của chữ số đó trong A đều nhìn thấy mọi vị trí của chữ số đó trong B. Vì hai ALS không thể cùng dùng RCC một lúc, ít nhất một ALS phải mất RCC và trở thành tập bị khóa.

Chính áp lực tập bị khóa đó tạo ra các loại bỏ. Nếu hai ALS còn chia sẻ một chữ số Z khác, thì Z phải xuất hiện trong ít nhất một trong hai ALS. Bất kỳ ô bên ngoài nào nhìn thấy mọi vị trí Z có thể có trong cả hai ALS đều không thể chứa Z.

ALS-XZ: quy tắc cốt lõi hai ALS

ALS-XZ dùng hai ALS. Chúng chia sẻ một ứng viên chung bị hạn chế X và một ứng viên chung thứ hai Z. Vì X không thể chiếm cả hai ALS, ít nhất một ALS buộc phải giải quyết mà không có X. Khi điều đó xảy ra, Z bị khóa vào ALS đó trừ khi nó đã bị buộc ở ALS kia.

Do đó, Z phải xuất hiện ở đâu đó trong hai ALS. Loại Z khỏi bất kỳ ô nào nhìn thấy mọi ứng viên Z trong cả hai ALS. Cấp 10 (Bậc thầy).

Các tập hợp gần như bị chặn: tìm các 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ì việc nhận ra các ALS tự nó đã hữu ích. Một ALS không phải là một loại bỏ cho đến khi nó tương tác với một ALS khác, một ô gốc, hoặc một giao điểm khối-đường. Kỹ năng thực tế là học cách nhận ra những nhóm ô nhỏ mà hợp các ứng viên của chúng chỉ lớn hơn số ô đúng một chữ số.

Hầu hết các kỹ thuật dựa trên ALS đều bắt đầu bằng việc lập danh mục các tập này, rồi kiểm tra xem các ứng viên chung của chúng có độ hiển thị cần thiết cho một RCC hay không.

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 kết nối nhiều ALS thông qua các RCC. Mỗi cặp lân cận có một ứng viên chung bị hạn chế, và chuỗi luân phiên việc ALS nào bị buộc trở thành bị khóa khi xét từng RCC.

Mục tiêu loại bỏ xuất hiện ở cả ALS đầu và ALS cuối. Nếu một ô bên ngoài nhìn thấy mọi vị trí mục tiêu có thể có ở cả hai đầu chuỗi, nó có thể bị loại. Cấp 11 (Cực hạn). ALS-XZ là phiên bản hữu ích ngắn nhất của ý tưởng này.

Sue de Coq: dạng giao nhau ALS

Sue de Coq khai thác giao điểm của một khối với một hàng hoặc cột. Giao điểm đó chứa hai hoặc ba ô thuộc cả hai nhà. Các ứng viên trong những ô giao điểm đó phải được cung cấp bởi phía hàng, phía khối, hoặc chính giao điểm.

Kỹ thuật này tìm hai tập hỗ trợ: một trong phần còn lại của hàng hoặc cột, và một trong phần còn lại của khối. Các ứng viên của chúng rời nhau, và cùng nhau chúng bao quát các ứng viên có thể chiếm giao điểm. Khi việc tính toán hoàn tất, các ứng viên khớp có thể bị loại khỏi những ô khác trong cùng hàng hoặc khối.

Cấp 9 (Bậc thầy).

Hoa chết: Kỹ thuật ALS Thân và Cánh hoa

Hoa chết bắt đầu với một thân ô có N ứng viên. Với mỗi ứng viên của thân, có một cánh hoa ALS khớp. Nếu thân nhận một ứng viên, cánh hoa ghép cặp của nó mất ứng viên đó và trở nên bị khóa.

Dù thân cuối cùng nhận giá trị nào, một trong các cánh hoa buộc phải vào trạng thái bị khóa. Nếu cùng một chữ số loại trừ xuất hiện trên tất cả các cánh hoa, thì chữ số đó phải được cung cấp bởi ít nhất một cánh hoa. Bất kỳ ô bên ngoài nào nhìn thấy mọi vị trí có thể của chữ số đó trên các cánh hoa đều có thể loại nó.

Cấp 11 (Cực khó).

Cách tìm các mẫu ALS

Liệt kê 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ệ. Với Sue de Coq, tập trung vào giao điểm khối-hàng. Với Hoa chết, bắt đầu từ các ô thân có ít ứng viên.

Xếp hạng độ khó

Các tập hợp gần như bị chặn: Cấp 9, Bậc thầy

Sue de Coq: Cấp 9, Bậc thầy

ALS-XZ: Cấp 10, Bậc thầy

Chuỗi ALS: Cấp 11, Cực khó

Hoa chết: Cấp 11, Cực khó

Tóm tắt

Các kỹ thuật ALS xây dựng trên hai khái niệm: Tập gần như bị khóa (N ô, N+1 ứng viên) và Ứng viên chung bị hạn chế. 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 đó trong các cấu hình khác nhau. Cùng nhau chúng tạo thành một trong những họ mạnh mẽ nhất để giải những câu đố khó nhất.