Открытые подмножества

Что такое голые подмножества в Судоку?

Голый подмножество — это группа из 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 объединенными кандидатами фиксируют эти цифры на месте, позволяя исключить их из всех других клеток в доме. От скромного Одиночка голая, который решает Ячейка сразу, через свободные пары и тройки, устраняющие кандидатов, до редкого Голый квадрат, который требует тщательного систематического поиска, эти техники составляют основу логического Судоку решения. Освоив их, вы получите надежные инструменты, применимые к головоломкам любого уровня сложности, и создадите основу для освоения еще более сложных стратегий, таких как скрытые подмножества, паттерны рыбы и цепочки.