Методика розв’язання головоломок судоку

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

Спершу рекомендується ознайомиться з термінологією гри судоку.

Одиничний кандидат

Всі комірки, що мають лише один кандидат, називаються одиничними:

Дуже важливо щоразу, після того як було визначене значення для якоїсь клітинки, впевнитись що це значення виключено як кандидат для пустих комірок, що входять в той самий ряд, колонку і регіон. (Програми подібні до Simple Sudoku роблять це автоматично).

Прихований одиничний кандидат

Дуже часто є лише один кандидат для того чи іншого рядка, колонки, або регіону, але це приховано серед інших кандидатів:

Наприклад, в даному прикладі (вгорі) бачимо, що кандидат 6 міститься лише в одній комірці (вона виділена жовтим кольором). Ми пам’ятаємо, що по правилам судоку, в кожному регіоні повинні бути всі числа від 1 до 9, і цифра 6 не є винятком. Тому в жовту комірку слід поставити 6.

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

Закритий кандидат

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

Оскільки, хоч одна з «зелених» комірок має отримати значення 2, ніякі інші комірки в цьому ряду не можуть мати це число. Тому 2 слід видалити з виділених жовтим кольором комірок.

Закритий кандидат 2

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

У лівому стовпчику кандидат 9 може стояти лише в одній з комірок середнього регіону. Тому одна з виділених зеленим кольором комірок має отримати значення 9 (інакше ліва колонка була б без 9) і число 9 можна виключити з решти клітинок цього регіону.

Гола пара

Якщо дві комірки в групі (рядку, стовпчику або регіоні) мають ідентичну пару кандидатів (і лише цю пару кандидатів), то ніякі інші комірки в цій групі їх мати не можуть. Ці два кандидата повинні бути виключені з інших комірок групи. У прикладі наведеному вище, кандидати 6 та 8 формують в межах ряду «голу пару» (виділено зеленим). Тому кандидати 6 та 8 можуть бути виключені з інших комірок цього ряду (жовта комірка).

«Голі трійки» та «голі четвірки» визначають по тому самому принципу, що і «гола пара».

Голі трійки

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

На малюнку розміщеному вище, виявлені спільні кандидати 1,4 і 6. Тому кандидати 1 і 4 у виділених жовтим клітинках можуть бути видалені.

Голі четвірки

Гола четвірка виникає тоді коли чотири клітинки в групі містять чотири спільні кандидати. Кожна клітинка не може мати більше чотирьох кандидатів. Кожному елементу «голої четвірки» не обов’язково мати всі чотири кандидати.

На малюнку вгорі «голу четвірку» утворюють клітинки виділені зеленим кольором. Спільні кандидати — 2, 5, 7 та 9. Тому кандидати 5 та 7 в виділених жовтим клітинках можуть бути видалені.

Приховані пари

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

На малюнку вгорі, кандидати 1 та 9 розміщені лише в виділених зеленим кольором клітинках регіону 3×3, і тому вони формують пару. Всі кандидати окрім 1 та 9 повинні бути виключені з цих двох клітинок, оскільки в одній із них має бути 1, а в інший 9.

Приховані трійки

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

На малюнку вгорі, кандидати 3, 6 і 7 знайдено тільки в клітинках виділених зеленим кольором. Тому всі інші кандидати можуть бути вилучені з цих трьох клітинок. Приховані трійки знаходити важко, але вони на щастя, рідко використовуються для рішення головоломок.

Приховані четвірки

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

Приховані трійки знаходити надзвичайно важко, навіть коли ви точно знаєте, що вони є. Спробуйте віднайти приховану четвірку на малюнку вгорі.

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

Х-крило

«X-крило» — позиція, коли один із кандидатів двічі (і лише двічі) зустрічається в двох рядках головоломки. До того ж ці кандидати мають розділяти дві колонки, що забезпечує формування прямокутного Х-крила. Дві колонки з двома (і лише з двома) клітинками, що містять однакових кандидатів (їх в колонках мають розділяють два рядка) також формують X-крило. Ці чотири клітинки — єдині можливі місця розташування для «справжніх» кандидатів в цих рядках або колонках. Інші подібні кандидати, розташовані по периметру прямокутника, утвореного «справжніми» кандидатами, повинні бути видалені. (Можливо ця позиція була названа X-крилом тому, що в кінцевому варіанті «справжні» кандидати мають знаходитись по діагоналі в протилежних кутах прямокутника).

Розглянемо приклад рішення «Х-крила» (малюнок вгорі). Як бачимо, для легкості сприйняття, із кандидатів відображено лише шістки (було застосовано фільтрування кандидатів — програма Simple Sudoku це підтримує).

Сині та яскраво-зелені клітинки формують класичне «X-крило» — перший та дев’ятий рядок мають лише по дві клітинки з кандидатом 6, їх розділяють дві колонки (сьома та восьма), кандидати утворюють прямокутник. «Справжніх» кандидатів представляють сині, або світло-зелені клітинки. Тому, інші кандидати в шостій та дев’ятій колонках потрібно видалити (їх виділено жовтим контуром).

Риба-меч

Комбінація «Риба-меч» є одним із варіантів позиції «X-крило» описаної вище:

«Риба-меч» — складна позиція утворена трьома рядками. Всі з цих рядків повинні мати не більше ніж три клітинки з однаковими кандидатами і використовувати спільні три колонки. Те саме стосується і «Риби-меч» утвореної трьома колонками — вони повинні мати не більше ніж три комірки з кандидатом і поділяти між собою три рядки. Ці колонки та рядки формують сітку, вузли якої є єдино можливими для розташування «справжніх» кандидатів. Решта кандидатів, що знаходяться на лініях перетину сітки мають бути видаленими.

Як завжди приклад. На малюнку вгорі, в результаті роботи фільтра кандидатів, показані лише 5-ки.

Отож, три колонки (друга, п’ята та восьма) мають кандидат 5 не більше ніж в трьох комірках (в даному випадку лише в двох). Всі комірки входять також в три рядки (перший, четвертий та дев’ятий). Позиція встановлена. Всі інші комірки з кандидатом 5, що входять до ліній перетину сітки (вони виділені жовтим контуром), потрібно видалити.

Рішення з кольоровими мітками

В цій комбінації нам цікаві кандидати, що знаходяться лише в одній або двох комірках групи (ряду, колонки або регіону 3×3). Одна з цих двох комірок є «вірною», а інша відповідно «хибною», але ми ще не знаємо котра. Як правило, в більшості головоломок судоку є багато з’єднаних пар. Інколи вони, з’єднуючись утворюють цілі складні ланцюжки, надаючи нам можливість виявити кандидатів, які можна безпечно вилучити.

Для того щоб показати зв’язок між цими комірками використаємо два кольори — синій та світло-зелений:

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

Також, якщо якийсь кандидат за межами складного ланцюжка зв’язаний колонкою, рядком або регіоном 3×3, з іншими двома комірками, що виділені альтернативними кольорами, то цей «неланцюговий» кандидат має бути вилучений.

Щоб зрозуміти все вищесказане розглянемо приклад (малюнок вгорі). Як бачимо, до головоломки було застосовано фільтрування по кандидату 5. Комірки відмічені літерами A та B формують з’єднану пару, оскільки вони є єдиними кандидатами 5 в восьмій колонці. Комірки B та C також утворюють з’єднану пару — вони є єдиними кандидатами 5 в правому нижньому регіоні. Нарешті C та D є єдиними кандидатами 5 в восьмому рядку і тому також формують з’єднану пару. Ці три з’єднані пари утворюють ланцюжок і можуть бути виділені альтернативними кольорами, як показано на малюнку. Комірка виділена жовтим контуром опосередковано відноситься до з’єднаних пар (A та D). Оскільки одна з виділених альтернативним кольором комірок має бути «вірною» то цей віддалений кандидат можна безпечно вилучити.

P.S.

Застосовуючи кроки описані вище можна розв’язати більшість головоломок Судоку. Але є також складні пазли, що не підвладні логічному розв’язанню. Єдиним методом їх рішення є «метод спроб та помилок» або, кажучи інакше «метод наукового тику». Також зустрічаються Судоку, що мають декілька рішень — це як правило «биті» та неправильно складені головоломки.

Використані матеріали:
Інструкція по рішенню Судоку
крок за кроком від Angus
Johnson (на англ.. мові).