Майже замкнені множини

Майже замкнені множини

Експерт

Що таке майже закрита множина?

ALS — це N клітин у одній доміні, що мають саме N+1 різних кандидатів. Це "майже заблоковане" — видаліть один кандидат, і воно стає відкритою підмножиною. Найпростіше ALS — це бізначене Клітинка (1 Клітинка, 2 кандидати). Усі клітини повинні належати до однієї доміни.

Що таке обмежений спільний кандидат?

RCC — це цифра, що з'являється в обох ALS A і ALS B, де кожен випадок цієї цифри в A бачить кожен випадок цієї цифри в B. Оскільки два ALS не можуть одночасно використовувати RCC, принаймні один ALS повинен втратити RCC і стати закритою множиною.

Саме це тиснення на закриту множину створює виключення. Якщо два ALS мають спільну цифру Z, то Z повинна з'являтися принаймні в одному з ALS. Жоден зовнішній Клітинка, що бачить всі можливі локації Z в обох ALS, не може містити Z.

ALS-XZ: Правило двох основних ALS

ALS-XZ використовує два ALS. Вони мають спільний обмежений загальний кандидат X і другий спільний кандидат Z. Оскільки X не може одночасно знаходитися в обох ALS, принаймні один ALS змушений вирішитися без X. Коли це відбувається, Z фіксується в цьому ALS, якщо воно ще не фіксоване в іншому.

Тому Z має з'явитися де-небудь в двох ALS. Видаліть Z з будь-якого Клітинка, який бачить всі кандидати Z в обох ALS. Рівень 10 (Майстер).

Майже замкнені множини: Пошук ALS

У додатку також зазначено Майже замкнені множини як техніку, оскільки впізнавання ALS корисне саме по собі. ALS не є виключенням, доки він не взаємодіє з іншим ALS, стеблом Клітинка або перетином блоку і лінії. Практична навичка полягає в тому, щоб навчитися виявляти невеликі групи клітин, об'єднання кандидатів яких має лише один більше цифри, ніж кількість клітин.

Більшість технік, заснованих на ALS, починаються з каталогізації цих множин, а потім перевірки, чи мають їхні спільні кандидати необхідну видимість для RCC.

Ланцюг ALS: Підключення кількох Майже замкнені множини

Деякий Ланцюг ALS з'єднує кілька ALS через RCC. Кожна сусідня пара має обмежену спільну кандидатуру, і ланцюг чергуються, яке ALS змушує стати заблокованим, коли розглядається кожен RCC.

Ціль видалення з'являється в обох першому і останньому ALS. Якщо зовнішній Клітинка бачить усі можливі місця розташування цілі на обох кінцях ланцюга, він може бути видалений. Рівень 11 (Екстремальний). ALS-XZ — найкоротший корисний варіант цієї ідеї.

Сю де Кок: Схема перетинання ALS

Сю де Кок використовує перетин блоку з рядком або стовпцем. Цей перетин містить дві або три клітинки, які належать одночасно до обох доменів. Кандидати в цих клітинках перетину повинні походити від сторони рядка, сторони блоку або самого перетину.

Ця техніка шукає дві допоміжні множини: одну в решті рядка або стовпця, і одну в решті блоку. Їхні кандидати не перетинаються, і разом вони охоплюють кандидатів, які можуть займати клітинки перетину. Після завершення підрахунку, співпадаючі кандидати можна видалити з інших клітинок у тому ж рядку або блоку.

Рівень 9 (Майстер).

Квітка смерті: Техніка ALS «Стебель і пелюстки»

Квітка смерті починається зі стеблом Клітинка, що має N кандидатів. Для кожного кандидата стебла існує відповідне пелюсткове ALS. Якщо стебло приймає один кандидат, його парне пелюсткове ALS втрачає цей кандидат і стає заблокованим.

Незалежно від того, яке значення прийме стебло, одне з пелюстків змушується перейти в стан блокування. Якщо одна й та сама цифра виключення з'являється на всіх пелюстках, то ця цифра повинна бути забезпечена принаймні одним пелюстком. Будь-який зовнішній Клітинка, що бачить кожну можливу появу цієї цифри на пелюстках, може виключити її.

Рівень 11 (Екстремальний).

Як знаходити шаблони ALS

Каталогуйте ALS у кожній клітині. Шукайте пари, що мають спільні кандидати з дійсними RCC. Для Сю де Кок, зосередьтеся на перетинанні блоку та лінії. Для Квітка смерті, почніть зі стовбурових клітин з незначною кількістю кандидатів.

Рівні складності

Майже замкнені множини: Рівень 9, Майстер

Сю де Кок: Рівень 9, Майстер

ALS-XZ: Рівень 10, Майстер

Ланцюг ALS: Рівень 11, Екстремальний

Квітка смерті: Рівень 11, Екстремальний

Огляд

Техніки ALS ґрунтуються на двох концепціях: майже замкненій множині (N клітин, N+1 кандидатів) та обмеженому спільному кандидаті. Майже замкнені множини надають основні елементи; ALS-XZ, ланцюги ALS, Сю де Кок, і Квітка смерті використовують ці елементи в різних конфігураціях. Разом вони утворюють одну з найпотужніших родин для вирішення найскладніших пазлів.