Час грати?

Грати в судоку!

Примусові сітки

ЕкстремальніКласичне + кілерКрок 37 з 384 хвилини читання

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

Що це за візерунок

Ланцюг іде однією лінією висновків. Сітка іде однією такою лінією для кожного варіанта початкової клітинки чи області, і в загальному випадку лінія може знову розгалужуватися: висновок може потребувати одразу двох попередніх, як-от «ця клітинка 4, а та 9, отже в блоці лишилося лише одне місце для 7». Перевірка всіх варіантів і робить сітки сильнішими за ланцюги, але повільнішими в перевірці.

Є два способи почати й два способи закінчити:

Починаєш ізПростежуєшЦе доводить
Клітинки з k кандидатамипо гілці на кандидатаусе, що спільне для всіх гілок
Цифри з k місцями в одній областіпо гілці на місцеусе, що спільне для всіх гілок

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

Коли його шукати

Лише коли все дешевше не спрацювало: одиначки, заблоковані множини, риби, крила, ланцюги й майже заблоковані множини. Сітки дорого простежувати й легко помилитися, тому це свідомий останній логічний крок, а не звичка. Обирай початкову клітинку з двома кандидатами та багатьма сусідами з двома кандидатами; гілки лишаються короткими, і все можна перевірити.

Як застосувати, крок за кроком

  1. Онови всі нотатки. Сітка на застарілому кандидаті нічого не доводить.
  2. Обери клітинку з двома кандидатами або цифру з двома місцями в області.
  3. Припусти перший варіант і випиши лише ті постановки, що справді примусові.
  4. Скасуй усе повністю, потім зроби те саме для другого варіанта.
  5. Порівняй гілки. Лиши будь-яку постановку чи виключення, спільні для них.
  6. Якщо гілка суперечить сама собі, одразу відкинь цього кандидата.

Розібраний приклад

Початок із клітинки

  1. Простіші техніки вичерпано. Придивись до H1, яка може бути лише 1, 5 або 7.

  2. H1 має бути 1, 5 або 7. Перевір кожне значення по черзі й стеж за 7 в C1.

  3. Гілка 1: H1 = 7. C1 ділить стовпець 1 з H1, тож не може бути 7.

  4. Гілка 2: H1 = 1. Тоді A1 не може бути 1, тож A1 це 7, і C1 не може бути 7 (знову стовпець 1).

  5. Гілка 3: H1 = 5. E1 втрачає 5 (стовпець 1), тож F3 єдине місце для 5 у блоці 4.

    Коли F3 = 5, F8 єдине місце для 8 у рядку F. Тоді C8 не може бути 8, тож C1 єдина 8 у рядку C.

    C1 = 8, тож C1 не 7.

  6. Пробні значення прибрано. Усі три гілки закінчуються тим, що C1 не 7.

    7 видалено з C1, бо кожне значення H1 її виключає.

Простіші техніки вичерпано. Придивись до H1, яка може бути лише 1, 5 або 7.

H1 містить , а ціль — 7 у C1. Кожне значення H1 простежуємо по черзі:

  • H1 = 7: C1 ділить стовпець 1 з H1, тож не 7.
  • H1 = 1: A1 не може бути 1, тож A1 — 7, і C1 не 7 з тієї самої причини про стовпець.
  • H1 = 5: E1 втрачає свою 5, тож F3 — єдина 5 у блоці 4. Тоді F8 — єдина 8 у рядку F, C8 не може бути 8, і C1 — єдина 8, що лишилась у рядку C. C1 = 8, тож C1 не 7.

Усі три гілки закінчуються тим, що C1 не 7, тож C1 втрачає свою 7. Ти так і не дізнаєшся, чим є H1: гілки зробили свою роботу й були відкинуті.

Початок із цифри в області

  1. Простіші техніки вичерпано. Придивись до сімок у блоці 7.

  2. Блоку 7 потрібна 7, і вона може стояти лише в G2, H2 або J3. Перевір кожне місце й стеж за 7 в A2.

  3. Гілки 1 і 2: якщо 7 стоїть у G2 або H2, A2 не може бути 7, бо всі три клітинки у стовпці 2.

  4. Гілка 3: J3 = 7. Тоді J3 не 5, і A3 стає єдиним місцем для 5 у стовпці 3.

    Коли A3 = 5, A2 єдине місце для 1 у рядку A. A2 = 1, тож вона не 7.

  5. Пробні значення прибрано. Де б блок 7 не поставив свою 7, A2 лишається без 7.

    7 видалено з A2.

Простіші техніки вичерпано. Придивись до сімок у блоці 7.

Блоку 7 потрібна 7, і вона може стояти лише в G2, H2 або J3. Ціль — 7 у A2:

  • 7 у G2 або H2: A2 ділить стовпець 2 з обома клітинками, тож не 7.
  • 7 у J3: тоді J3 не 5, тож A3 — єдина 5 у стовпці 3. З A3 = 5 клітинка A2 — єдина 1 у рядку A, тож A2 = 1 і не 7.

Куди б блок 7 не поставив свою 7, у A2 немає 7, тож A2 її втрачає.

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

Типові помилки

  • Лишати позначки однієї гілки на сітці, коли починаєш наступну. Кожна гілка має починатися з тієї самої недоторканої позиції.
  • Іти за «ймовірно» замість примусової постановки. Записувати можна лише одиначки й заблоковані виключення.
  • Пропустити кандидата початкової клітинки. Пропусти одну гілку, і згода нічого не варта.
  • Сприймати суперечність в одній гілці як доказ висновків інших гілок.

Де ти його зустрінеш

Примусові сітки — це те, чого вимагають наші найскладніші сітки. Чекай їх у легендарних головоломках, і лише після того, як ланцюгові техніки на кшталт 3D Medusa уже спробовано. Усе, що розв'язує сітка, у принципі розв'язала б і коротша техніка. Сітка потрібна тоді, коли цієї коротшої техніки не знайти.