Голі підмножини

Що таке голі підмножини в Судоку?

Гола підмножина — це група з N клітин у одній домені (рядку, стовпці або блоку), кандидати яких разом містять саме N різних цифр. Оскільки ці N цифр мають заповнити ці N клітини, вони не можуть з’являтися в жодній іншій Клітинка цього домену. Це дозволяє безпечно видалити ці цифри з решти клітин. Слово "гола" означає, що кандидати повністю видимі і відкриті. Вам не потрібно шукати цифри, приховані серед інших кандидатів. Підмножина сама вказує на себе через олівцеві позначки в цих клітинах. Існує чотири методи голої підмножини, по одному для кожного можливого розміру групи: - Голий одиниці (N=1) — одна Клітинка з одним кандидатом - Гола пара (N=2) — дві клітини, кандидати яких разом складають саме дві цифри - Голий триплет (N=3) — три клітини, кандидати яких разом складають саме три цифри - Голий квадрат (N=4) — чотири клітини, кандидати яких разом складають саме чотири цифри Ці чотири методи утворюють родину. Вони мають однакову основну логіку і відрізняються лише кількістю клітин. Коли ви зрозумієте основну ідею, більші підмножини стають природним розширенням простіших.

Основна принцип: чому прозорі підмножини працюють

Логіка, що лежить в основі голих підмножин, ґрунтується на фундаментальному аргументі підрахунку, який іноді називають принципом Діріхле. У простій мові: якщо у вас є N вільних місць і саме N елементів, які потрібно розмістити в них, кожен елемент займає рівно одне місце, і інші елементи не можуть займати ці місця. Розглянемо рядок з дев'яти клітин. Кожна нерозв'язана Клітинка має набір кандидатів — цифри, які ще можна дозволити в цій Клітинка. Припустимо, ви знайшли дві клітини в цьому рядку, кандидати яких беруться з одного й того ж двохцифрового набору, скажімо {4, 6}. Одна з цих клітин має містити 4, а інша — 6. Немає місця для іншого розташування. Це означає, що жодна інша Клітинка у рядку не може містити 4 або 6, оскільки обидві цифри повністю використані цими двома клітинами. Те саме міркування застосовується і до більших множин. Три клітини, кандидати яких разом складають рівно три цифри, визначають, що ці три цифри повністю належать цим трьом клітинам. Чотири клітини з чотирма загальними кандидатами визначають, що всі чотири цифри належать цим чотирьом клітинам. У кожній Клітинка заборонені цифри можна видалити з усіх інших клітин у спільному домені. Цей принцип застосовується однаково, незалежно від того, чи є домен рядком, стовпцем чи блоком 3x3. Єдине вимога — всі N клітин повинні належати до одного домену.

Голий одиниці: Основа розв'язання Судоку

Голий одиниці — найпростіший можливий відкритий підмножина. Він виникає, коли в Клітинка залишається лише одна можлива цифра в її кількості кандидатів. Оскільки є лише одна цифра, яка може бути дозволеною для цього Клітинка, ця цифра є рішенням для Клітинка. Кожен розв'язувач Судоку, незалежно від того, людина чи алгоритм, залежить від відкритих одиниць. Це останній етап ланцюжка виключень: після того, як усі обмеження з рядка, стовпця та блоку видали неможливі цифри, єдиний залишений кандидат є відповіддю. Щоб знайти Голий одиниці, потрібно докладно відстежувати кількість кандидатів для кожного Клітинка. Клітинка починається з до дев'яти можливих кандидатів. Коли ви розміщуєте цифри в інших місцях на дошці, кандидати видаляються: - Якщо цифра розміщена де-небудь в тому ж рядку, видаліть її з кандидатів Клітинка. - Якщо цифра розміщена де-небудь в тому ж стовпці, видаліть її з кандидатів Клітинка. - Якщо цифра розміщена де-небудь в тому ж 3x3-блоку, видаліть її з кандидатів Клітинка. Коли ці виключення зменшують Клітинка до одного кандидата, ви знайшли Голий одиниці. Розгляньте Клітинка R5C3 в частково розв'язаній пазлі. Обмеження рядка, стовпця та блоку видаляють наступні цифри: - У рядку 5 вже є: 1, 3, 5, 8 - У стовпці 3 вже є: 2, 6, 9 - У блоку 4 (середній лівий блок) вже є: 7 Всього видалені цифри: 1, 2, 3, 5, 6, 7, 8, 9. Єдиний залишений кандидат — 4. Клітинка R5C3 має бути 4. Це Голий одиниці. Відкриті одиниці слід перевіряти першими після кожного кроку. Кожен раз, коли ви розміщуєте цифру, вона може зменшити сусідні клітинки до одного кандидата. У легких пазлах ланцюги відкритих одиниць можуть розв'язати великі частини дошки без використання інших методів. Навіть у складних пазлах відкриті одиниці очищують дошку після того, як більш складні методи видаляють кандидатів.

Гола пара: Дві клітини, дві кандидати, потужні виключення

Пара без приховування виникає, коли дві клітинки в одній домені містять саме однакові дві кандидатури і ніяких інших кандидатур. Оскільки ці дві цифри мають бути розміщені саме в цих двох клітинках, ви можете видалити обидві цифри з усіх інших клітинок у цьому домені. Пари без приховування — одна з найбільш поширених стратегій середніх рівнів. Вони часто з’являються і часто дозволяють зробити значний крок у розв’язанні, видаливши кандидатів, які блокують інші методи. Припустимо, що дві клітинки в рядку 1 містять кандидатури {4, 6} і ніяких інших кандидатур: - R1C2 має кандидатури: {4, 6} - R1C7 має кандидатури: {4, 6} Одна з цих клітинок буде 4, а інша — 6. Ми ще не знаємо, яка саме, але ми точно знаємо, що цифри 4 і 6 повністю використані цими двома клітинками. Тому жодна інша клітинка в рядку 1 не може містити цифри 4 або 6. Якщо R1C4 містить кандидатури {3, 4, 6, 9}, вона може бути скорочена до {3, 9} шляхом видалення 4 і 6. Якщо R1C8 має кандидатури {2, 6}, вона може бути скорочена до {2}. Це скорочення до однієї кандидатури є саме стратегією, яка вирішує клітинку безпосередньо. Шукайте клітинки з саме двома кандидатурами в кожному домені. Коли ви знаходите дві клітинки в одному домені з ідентичними двокандидатними наборами, ви маєте пару без приховування. Оскільки клітинки з лише двома підписами відзначаються візуально, пари без приховування є однією з найпростіших середніх стратегій для виявлення. Корисна звичка: коли ви помічаєте пару без приховування з лише двома кандидатурами, одразу перевірте, чи не має жодна інша клітинка в тому самому рядку, стовпці або блоку ті самі пари.

Голий триплет: Три клітинки, три кандидати, ніжна гра

У Голий триплет виникає, коли три клітинки в одній домені мають кандидатів, що повністю беруться з однієї групи з точнісно трьох цифр. Загальна множина всіх кандидатів у трьох клітинках містить саме три різні цифри. Ось ключова інсайт, який застає багатьох розв'язувачів в безпідставності: кожна окрема Клітинка не повинна містити всі три цифри. Правильна Голий триплет може містити клітинки з лише двома з трьох цифр. Важливо те, що об'єднана множина всіх кандидатів у трьох клітинках має саме три різні значення. Багато гравців спочатку вчаться виявляти голі пари, а потім припускають, що голі трійки вимагають трьох клітин, кожна з яких містить ті самі три кандидати, як-то {1, 3, 7} у всіх трьох клітинках. Хоча це один із правильних варіантів Голий триплет, це не єдиний і навіть не найпоширеніший. Розгляньмо ці три клітинки в стовпці 5: - R2C5: {1, 3} - R4C5: {1, 7} - R8C5: {3, 7} Загальні кандидати — {1, 3, 7}, що саме три цифри в трьох клітинках. Це правильна Голий триплет, навіть якщо жодна окрема Клітинка не містить усі три цифри. Логіка та ж, що й у голих пар. Ці три цифри мають заповнити ці три клітинки в певному порядку. Одна Клітинка отримає 1, одна — 3, одна — 7. Тому цифри 1, 3 і 7 можна виключити з усіх інших Клітинка в стовпці 5. Почніть з виявлення клітинок з двома або трьома кандидатами. У певному домені, якщо ви знайдете три клітинки, чиї загальні кандидати утворюють множину з саме трьох цифр, ви маєте Голий триплет. Практичний підхід: 1. У кожному домені перелічіть всі нерозв’язані клітинки з трьома або менше кандидатами. 2. Виберіть будь-яку комбінацію трьох таких клітин. 3. Знайдіть об’єднання їх кандидатів. Якщо об’єднання має саме три цифри, це Голий триплет. Оскільки існує кілька можливих комбінацій, голі трійки вимагають більш уважного сканування, ніж голі пари. Це частина того, що робить їх складнішою технікою.

Голий квадрат: Чотири клітинки, чотири кандидати, максимальна складність

Голий квадрат — найбільший звичайно використовуваний голий підмножина. Він виникає, коли чотири клітинки в одній сусідній групі мають кандидатів, що повністю беруться з однієї тієї ж групи зовсім чотирьох цифр. Як і випадки з трійками, окремі клітинки не повинні містити всі чотири цифри. Ключове умову полягає в тому, що об'єднання кандидатів у всіх чотирьох клітинках дорівнює точно чотирьом різним значенням. Логіка та ж, що і для менших голих підмножин. Чотири цифри повинні заповнити чотири клітинки. Ці цифри не можуть з'явитися ніде інше в групі. Голі четвірки рідко виявляються при звичайному огляді. З чотирма клітинками і чотирма цифрами існує багато можливих комбінацій для перевірки. У групі з шістьма нерозв'язаними клітинками існує 15 можливих способів вибрати чотири з них. Перевірка кожної комбінації у розумі є нудною. Більшість розв'язувачів, які знаходять голі четвірки, роблять це або через систематичну перевірку, або спочатку помічають, що залишилися клітинки утворюють доповнюючу приховану підмножину. Незважаючи на свою рідкість, голі четвірки з'являються в справжніх пазлах, особливо тих, що оцінюються на середній або складній рівень складності. Маючи цю техніку в своєму арсеналі, ви не застрягнете, коли простіші методи вже вичерпані.

Як виявляти голі підмножини: практичні поради щодо сканування

Ефективне виявлення голих підмножин вимагає структурованого підходу замість випадкового сканування. Ось технології, які використовують досвідчені розв'язувачі: Почніть з малих кількостей кандидатів: клітини з меншою кількістю кандидатів більш ймовірно беруть участь у голих підмножинах. Клітина з двома кандидатами може бути частиною пари, трійки або четвірки. Клітина з п'ятьма кандидатами менш корисна, оскільки вона вносить занадто багато цифр у об'єднання. Спочатку перевірте кожну клітину на дві кандидати. Перевірте на збіг пар. Потім досліджуйте клітини з двома або трьома кандидатами разом, щоб знайти трійки. Працюйте по клітинам: виберіть рядок, стовпець або блок і розгляньте всі нерозв'язані клітини разом. Запишіть їх кандидатів. Шукайте групи клітин, кандидати яких перетинаються в малих діапазонах цифр. Використовуйте перевірку підрахунку: для будь-якої групи з N клітин, які ви підозрюєте утворюють голу підмножину, підрахуйте кількість різних цифр у їх об'єднаних кандидатах. Якщо кількість дорівнює N, ви знайшли голу підмножину. Якщо кількість перевищує N, ці клітини не утворюють голу підмножину. Перевіряйте після кожного виключення: коли інша техніка видаляє кандидатів з Клітинка, повторно перевірте цей Клітинка. Виключення може створити нову голу підмножину, яка раніше не була помітною. Багато голих пар виникають як побічний ефект попередніх виключень. Шукайте доповнення: якщо в клітині є K нерозв'язаних клітин і ви підозрюєте існування голої підмножини, але не можете знайти її безпосередньо, спробуйте подивитися на доповнення. Виявлення прихованої підмножини розміром M автоматично означає існування голої підмножини розміром K - M.

Зв'язок між голими підмножинами та прихованими підмножинами

Голі підмножини та приховані підмножини — це дві сторони однієї медалі. Зрозуміння їхньої дуальності глибше відчуває ваше розуміння логіки Судоку і може допомогти знайти патерни, які інакше можуть залишитися непоміченими. Прихована підмножина виникає, коли N цифр у клітці з'являються лише в N певних клітинках. Ці цифри "приховані", оскільки ці клітинки можуть містити інші кандидати. Вилучення видаляє зайві кандидати з цих N клітинок, залишаючи лише приховані цифри. У будь-якій клітці з K нерозв'язаними клітинками, якщо існує гола підмножина розміром N, то автоматично існує прихована підмножина розміром K - N. Ці дві підмножини є доповнювальними: вони розподіляють нерозв'язані клітинки та решту цифр на дві не перетинаючіся групи. Наприклад, розглянемо рядок з 6 нерозв'язаними клітинками. Якщо дві з цих клітинок утворюють Гола пара, то решта чотирьох клітинок утворюють Прихована четвірка (або еквівалентно, існує Голий квадрат серед виключених цифр цих чотирьох клітинок). Ви можете знайти будь-яку з них і застосувати відповідні вилучення. Ця дуальність означає, що ви маєте дві шляхи до однієї і тієї ж вилучення. Якщо клітка має багато нерозв'язаних клітинок, мала гола підмножина (пара або трійка) легше помітити, ніж велика прихована підмножина. Навпаки, якщо клітка має мало нерозв'язаних клітинок, Прихована пара може бути легше знайти, ніж шукати доповнюючу Голий квадрат. Досвідчені розв'язувачі переймаються між голим і прихованим поглядами залежно від того, який підхід більш практичний у даній ситуації. Здатність бачити обидві сторони дає вам значну перевагу.

Прогресія складності: від початківця до продвинутого

Чотири техніки голого підмножини охоплюють різні рівні складності, що відображає, наскільки складніше їх знаходити при збільшенні розміру групи: Голий одиниці (N=1): Рівень 2, Легко Гола пара (N=2): Рівень 3, Легко Голий триплет (N=3): Рівень 4, Середній Голий квадрат (N=4): Рівень 5, Складно Зростання складності не пов'язане з логікою, яка однакова для всіх Клітинка, але зі складністю пошуку: Голий одиниці: Вам потрібно перевірити лише одну Клітинка. Якщо вона має одну кандидату, ви вже закінчили. Не потрібно шукати комбінації. Гола пара: Вам потрібно знайти дві клітинки з однаковими кандидатами. У клітці з шістьма нерозв'язаними клітинками є 15 можливих пар для перевірки. Але оскільки ви шукаєте клітинки з саме двома однаковими кандидатами, візуальний патерн відзначається і легко впізнається. Голий триплет: Вам потрібно знайти три клітинки, сума кандидатів яких становить три цифри. У клітці з шістьма нерозв'язаними клітинками є 20 можливих трійок. Пошук складніший, оскільки клітинки не повинні мати однакові набори кандидатів. Голий квадрат: Вам потрібно знайти чотири клітинки з потенційно багатьох нерозв'язаних клітинок. Кількість комбінацій зростає, і обчислення чотирицифрових об'єднань складніше здійснювати у розумі. Більшість четвірок знаходять опосередковано, або шляхом систематичного підрахунку кандидатів, або шляхом виявлення доповнюючої Прихована пара. Оцінка складності пазлів часто залежить від технік, необхідних для їх розв'язання. Пазл, який потребує лише голого одиниці та пар, оцінюється як легкий. Пазл, що потребує голого трійки, вважається середнім. Пазл, що вимагає Голий квадрат, є щонайменше складним.

Поширені помилки та як їх уникнути

Помилка 1: Очікування, що всі клітинки містять усі цифри Найпоширеніша помилка при роботі з голими трійками та четвірками — це припущення, що кожна Клітинка у підмножині повинна містити всі N цифр. Це неправильно. Гола Голий триплет з клітинками {1,3}, {1,7} і {3,7} є повністю допустимою, навіть якщо жодна Клітинка не містить усіх 1, 3 і 7. Як уникнути: Завжди перевіряйте об'єднання кандидатів, а не окремі клітинки. Порахуйте різні цифри, що з'являються в усіх клітинках групи. Якщо кількість дорівнює кількості клітин, це гола підмножина, незалежно від того, як цифри розподілені між окремими клітинками. Помилка 2: Плуття голих і прихованих підмножин Гола Гола пара має N клітин з кандидатами, обмеженими N цифрами. Прихована Прихована пара має N цифр, обмежених N клітинами, але ці клітини можуть мати додаткові кандидати. При голій Гола пара ви видаляєте цифри пари з інших клітин у домені. При прихованій Прихована пара ви видаляєте цифри, що не належать парі, з клітин самої пари. Як уникнути: Задайте собі питання: «Чи дивлюся я на клітинки з обмеженими кандидатами (голі) чи на цифри з обмеженими місцями (приховані)?» Напрямок обмеження визначає тип підмножини, яку ви знайшли. Помилка 3: Видалення з неправильних клітин Коли ви знаходите голу Гола пара {4, 6} у клітинках R1C2 і R1C7, ви видаляєте 4 і 6 з інших клітин у рядку 1. Ви не видаляєте інші кандидати з R1C2 і R1C7. Кандидати Гола пара залишаються незмінними у клітинках підмножини. Як уникнути: Пам'ятайте правило: голі підмножини видаляють свої цифри з клітин поза підмножиною. Приховані підмножини видаляють цифри, що не належать підмножині, з клітин усередині підмножини. Помилка 4: Забуття перевірки всіх спільних доменів Дві клітинки можуть мати більше одного спільного домену. Наприклад, R1C1 і R1C3 мають спільні домени — рядок 1 і блок 1. Якщо вони утворюють Гола пара, ви можете видалити цифри пари з інших клітин у рядку 1 і з інших клітин у блоку 1. Не обмежуйте видалення лише одним доменом. Як уникнути: Для кожної голої підмножини, яку ви знаходите, перевірте, які домени спільно мають всі клітини підмножини. Застосовуйте видалення у кожному спільному домені.

Коли використовувати голі підмножини в своєму розробленні

Підмножини повинні перевірятися в порядку від найменшого до найбільшого: 1. Найперше перевірте голі одиниці. Після кожного розміщення, знову шукайте нові голі одиниці. Вони безкоштовні та миттєві. 2. Найперше голі пари. Коли більше немає голих одиниць, шукайте пари в кожному рядку, стовпці та блоку. Це найпоширеніший проміжний метод і часто відкриває додаткові голі одиниці. 3. Найперше голі трійки. Коли пари недостатні, розширте пошук на трійки. Зосередьтеся на клітках, де кілька клітин мають дві або три кандидати. 4. Найперше голі четвірки. Шукайте четвірки лише тоді, коли менші підмножини та інші методи вичерпані. Оскільки вони складні, спочатку перевірте приховані пари або трійки, оскільки вони можуть бути легшими для знаходження і виявляти ту саму інформацію через принцип двоїстості. Дотримуючись цієї послідовності, ви застосовуєте найпростіші та найефективніші методи спочатку, зберігаючи ментальні зусилля для тих випадків, коли вони справді потрібні.

Огляд

Голі підмножини — це сімейство чотирьох Судоку технік, що об'єднані однією елегантною принципом: N клітин у доміні, що мають саме N об'єднаних кандидатів, фіксують ці цифри на місці, що дозволяє видалити їх з усіх інших клітин у доміні. Від скромного Голий одиниці, що вирішує Клітинка відразу, через голі пари та трійки, що видаляють кандидатів, до рідкісного Голий квадрат, що вимагає уважного систематичного пошуку, ці техніки утворюють основу логічного __PH4 вирішення. Освоївши їх, ви отримаєте надійні інструменти, які застосовуються до пазлів усіх рівнів складності, і створите основу для вирішення навіть більш складних стратегій, таких як приховані підмножини, шаблони риб і ланцюги.