майже замкнені множини
майже замкнені множини
Пов'язані техніки
Що таке майже замкнений набір?
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. Якщо стебло бере одного кандидата, його парна пелюстка втрачає цього кандидата й стає заблокованою.
Хоч би яке значення зрештою взяв стебло, одна з пелюсток змушена перейти в заблокований стан. Якщо той самий цифровий виняток з'являється в усіх пелюстках, то цю цифру має забезпечити принаймні одна пелюстка. Будь-який зовнішній клітинка, що бачить кожен можливий екземпляр цієї цифри в пелюстках, може її вилучити.
Рівень 11 (Екстремальний).
Як знаходити ALS-шаблони
Каталогізуйте ALS у кожному будинку. Шукайте пари, що мають спільних кандидатів із чинними RCC. Для Сю де Кок зосередьтеся на перетинах блоку й лінії. Для квітка смерті починайте з клітинок стебла з небагатьма кандидатами.
Рейтинги складності
майже замкнені множини: рівень 9, майстер
Сю де Кок: рівень 9, майстер
ALS-XZ: рівень 10, майстер
Ланцюг ALS: рівень 11, екстремальний
квітка смерті: рівень 11, екстремальний
Підсумок
Техніки ALS будуються на двох поняттях: майже заблокований набір (N клітинок, N+1 кандидатів) і обмежений спільний кандидат. майже замкнені множини дають будівельні блоки; ALS-XZ, ланцюги ALS, Сю де Кок і квітка смерті використовують ці блоки в різних конфігураціях. Разом вони утворюють одну з найпотужніших родин для розв'язування найскладніших головоломок.
Пов'язані техніки