Видаліть одну цифру з Судоку — і, можливо, зробите його складнішим. Видаліть неправильну — і можете знищити єдину відповідь пазлу. Десь між заповненою сіткою та порожнім аркушем є жорстка межа: 17 початкових підказок. Чому Судоку зупиняється на цьому?

Відповідь починається з запитання, яке легко пропустити: чи має ваш пазл лише одне розв’язання?

Одна повністю заповнена сітка, одна відповідь

У класичному Судоку 9×9 кожен рядок, кожен стовпець і кожен 3×3 бокс мають містити цифри від 1 до 9 рівно по одному разу. Це стандартні правила, опубліковані Nikoli. Цифри, які вже надруковані в сітці, називаються given, або підказками.

Заповнена сітка може відповідати всім цим правилам, але при цьому не бути єдиною можливою відповіддю на ваш набір підказок. Якщо підходять два різні доповнення, у гравця не буде способу здогадатися, яке саме доповнення мав на увазі той, хто створив пазл.

Саме тому унікальність так важлива. Добре сформований класичний Судоку дає вам достатньо інформації, щоб визначити рівно одну заповнену сітку. Якщо ви тільки починаєте, наш посібник, як грати в Судоку — гарне місце, щоб стартувати.

Подивіться, як одна підказка змінює все

Ось навмисно майже завершений пазл. Точка позначає порожню клітинку.

5 3 4 | 6 . 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | . . 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9

У нього 78 підказок і одне розв’язання. У верхньому рядку потрібна 7. Тоді в четвертому рядку потрібна 7 у четвертому стовпчику і 6 у п’ятому.

Тепер видаліть 6 у рядку один, стовпчик чотири. Порожні чотири клітинки, і підходять два варіанти:

КлітинкаДоповнення AДоповнення B
Рядок 1, стовпчик 467
Рядок 1, стовпчик 576
Рядок 4, стовпчик 476
Рядок 4, стовпчик 567

Усі інші цифри лишаються тими самими. Обидва доповнення задовольняють усі рядки, стовпці, бокси та решту підказок. Ці чотири клітинки утворюють прямокутник, у якому 6 і 7 можна поміняти місцями, не порушуючи жодного правила. Ми перевірили кількість розв’язань: у першого пазлу було рівно одне; після видалення — стало рівно два.

Видалення підказки не може знецінити розв’язання, яке вже працювало: воно все одно задовольняє всі інші підказки. Те, що видалення може зробити, — це «відкрити двері» для іншої відповіді. Навіть цей пазл із 77 даними підказками є неоднозначним, тож лише велика кількість підказок сама по собі не гарантує унікальність.

Чому 17 — мінімум

Гері Макгуайр (Gary McGuire), Бастіан Туґеманн (Bastian Tugemann) і Жиль Сіваріо (Gilles Civario) довели, що жодне класичне Судоку 9×9 із 16 підказками не має рівно одного розв’язання. Їхня оригінальна наукова стаття описує вичерпний комп’ютерний пошук. Існують пазли з 17 підказками, які розв’язуються однозначно, тож 17 — це мінімум.

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

Чому заборона 16 також означає заборону менших кількостей? Якщо б існував менший пазл з одним розв’язанням, ви могли б додати в нього правильні підказки з цього розв’язання, доки не стало 16. Додавання таких підказок зберегло б унікальну відповідь, що суперечить результату.

Як довести, що менший пазл не існує?

Знайти один пазл із 17 підказками — означає показати, що таке можливе. Довести, що 16 не працює, — це значить виключити всі можливості.

Дослідники системно шукали завершені сітки, враховуючи еквівалентні сітки. Їхній метод спирався на unavoidable sets (неуникні множини): групи клітинок, які мають містити підказку, щоб запобігти альтернативному доповненню. Вони розробили ефективний алгоритм для переліку hitting sets (множин «пробиття») — виборів, які перетинають ці групи, — і перевірили кандидатні множини підказок на унікальність. У статті пояснюється метод.

Прямокутник вище дає маленьку ілюстрацію ідеї. Залиште всі чотири клітинки без підказок — і два доповнення виживуть. Зафіксуйте хоча б одну з цих клітинок — і ви заблокуєте саме той обмін. У разі «рідкого» пазлу багато можливих альтернатив треба блокуєти одночасно.

Мінімальна кількість підказок не означає максимальну складність

Кількість підказок відповідає на запитання: «скільки інформації надруковано?». Вона не говорить вам, яку дедукцію ви помітите наступною. Порахувати givens недостатньо, щоб зрозуміти, чи наступний крок буде очевидним одиничним ходом або патерном, який ви ще не вчили.

Є ще одна корисна різниця: minimum і minimal. Мінімум — це найменша кількість підказок, можлива в класичному Судоку. Мінімальний пазл — це такий, у якому видалення будь-якої підказки позбавляє унікальності. Називати пазл мінімальним не означає, що в ньому рівно 17 підказок.

Для вашої наступної гри спробуйте пояснювати кожне розміщення перед тим, як його робити: «Це єдина клітинка в боксі, де може бути 4». Якщо ви поки не можете пояснити хід, перевірте кандидати або спробуйте техніку з нашого посібника з розв’язування Судоку.

Наступного разу, коли ви побачите «рідкий» Судоку, порахуйте підказки — а потім знайдіть причину, чому кожна з них має значення.

ДОЛУЧАЙТЕСЯ ДО РОЗМОВИ

Коментарі

0

Поділіться думкою, поставте запитання або допоможіть іншому гравцеві.

Перевіряємо вхід…

Завантажуємо коментарі…