Головоломка набула шаленої всесвітньої популярності саме завдяки простим умовам і тому, що вона схожа на кросворд, але на відміну від нього вона не прив’язана до мови, культурного коду чи набору знань. Все, що треба, щоб почати розв’язувати головоломку – це знання цифр плюс трохи логіки та здорового глузду. При цьому можна розв’язувати головоломку на папері або на комп’ютері.
Паперовий збірник можна придбати в будь-якому газетному кіоску будь-якої країни. Також судоку часто зустрічається у щоденній пресі на сторінці розваг. Історично саме щоденна преса зробила судоку світовим феноменом. Газети досі щодня друкують головоломки різного рівня складності, а також ведуть їх популярні онлайн-версії.
Існують судоку різного рівня складності, з різною кількістю початкових цифр, але в будь-якому разі головоломка повинна мати розв’язок, і при цьому єдиний.
Виникає питання – як створюється головоломка таким чином, щоб вона мала єдиний розв’язок? У теперішній час головоломки судоку створюються за допомогою комп’ютерних програм, при цьому в основі алгоритму лежить метод оберненої індукції. За основу береться будь-яка правильно заповнена цифрами таблиця, і з неї послідовно видаляються цифри, при цьому на кожному кроці робиться перевірка, чи єдиним чином можна відновити вихідну таблицю. Якщо ні – то видалена цифра повертається на місце та видаляється інша.
Історія виникнення та розвитку Судоку
Історія судоку охоплює понад два століття і пов'язує три континенти: Європу, Америку та Азію. Гра пройшла шлях від математичного прикладу до масового культурного феномена.
1783: Народження концепції у Швейцарії. Математик Леонард Ейлер описує "латинський квадрат" – матрицю, в якій присутні різні елементи так, що кожен рядок та кожнен стовпець матриці містить рівно один елемент кожного типу.
1890-і роки: Французький етап. Газети Парижа публікують числові пазли, схожі на латинські квадрати, готуючи аудиторію до числових головоломок.
1979: Створення сучасної сітки в США. Архітектор Говард Гарнс додає поділ на блоки 3×3 і публікує гру під ім'ям «Number Place». Однак на даному етапі це було рядовою публікацією, суспільний масовий інтерес до головоломки виник через п’ять років.
1984: Японська модернізація. Макі Кадзі У 1984 році натрапив на американську гру "Number Place". Гра йому сподобалася, але назва здалася нудною. Він придумав японську фразу «Судзі ва докусин ні кагіру» («Цифри повинні бути самотніми»), скоротивши її до «Судоку». Несподівано гра розійшлася світом, наче вірус. Кадзі хотів, щоб гра приносила радість та задоволення, була зрозумілою для дітей і не вимагала складних математичних розрахунків. Іронія успіху полягає в тому, що Кадзі став всесвітньо відомою особою, але при цьому він не оформив міжнародний патент на назву «Судоку», тому не заробив мільйонів на його всесвітньому бумі. Сам він ставився до цього по-філософськи, радіючи тому, що мільйони людей по всьому світу стали щасливішими завдяки його улюбленій справі.
1997–2004 роки: Цифровізація. Новозеландець Уейн Гулд розробляє комп'ютерну програму для миттєвої генерації полів. 2004: Глобальний бум. Британська газета The Times публікує перше судоку Гулда, запускаючи хвилю всесвітньої судоку-манії.
2006 рік: Офіційне визнання. В Італії проходить перший в історії Чемпіонат світу з судоку. Надалі чемпіонат набуває популярності та проходить щорічно.
Судоку в цифрах
Виявляється, що існує порядку 6,67·1021 різних початкових позицій, які мають однозначний розв’язок. Якщо розбити позиції на типи так, щоб в один тип об’єднати варіанти, які можна отримати один з одного шляхом повороту та дзеркальної симетрії початкової матриці, а також шляхом перестановки цифр, то залишиться порядку 5,47·109 типів варіантів.
Мінімальна кількість підказок у судоку, що має єдиний розв’язок, складає 17. Всі судоку з 16 підказками, які мають розв’язок, завжди мають по декілька розв’язків.
Розв’язок буде гарантовано єдиним тільки при 78 підказках.
Термінологія судоку
Клітина – найменший неподільний осередок, всього їх 81 у сітці. Кожна клітина являє собою перетин трьох одиниць, оскільки вона знаходиться в одному рядку, одному стовпці і одному блоці.
Рядок – горизонтальна одиниця з 9 клітин, яка повинна містити всі 9 цифр. У сітці їх 9. R1 – верхній рядок, а R9 – нижній рядок.
Стовпець – вертикальна одиниця із 9 клітин, яка повинна містити всі 9 цифр. Знову ж таки, у сітці їх 9. C1 – найлівіший стовпець, а C9 – найправіший. стовпець.
Блок, або Квадрат – набір із 3 x 3 клітин, який також повинен містити всі 9 цифр. У сітці їх 9. B1 – верхній лівий, а B9 – нижній правий, зліва направо по горизонталі.
Дім – визначена область з 9 клітин, яка повинна містити всі 9 цифр. У сітці їх 27. Це спільна назва для рядка, стовпця або блоку.
Цифра – всі визначені числа, що стоять у клітинах, які або дані, або знайдені в процесі розв’язку головоломки. Позначається великим шрифтом.
Кандидат – потенційне цифрове значення, що може належати клітині. Позначається дрібним шрифтом.
Виключення – видалення кандидата, який, як було визначено, не може належати даній клітині.
Бачити клітину – кажуть, що одна клітина бачить іншу, якщо вона знаходиться з нею в одному домі (тобто рядку, стовпчику або блоці).
Нотація судоку
Рядки (R) таблиці нумеруються зверху вниз та стовпці (C) нумеруються зліва направо. Якщо треба вказати якусь клітину, то пишеться номер її рядка та стовпця, наприклад, ліва верхня клітина має позначку R1C1. Блоки нумеруються зліва-направо, зверху-вниз.
Розв’язок судоку на комп’ютері
До переваг такого методу розв’язку в порівнянні з паперовим слід відзначити такі: головоломки безкоштовні та завжди поряд з вами, разом з вашим телефоном. За бажанням можна виводити сітку потенційних кандидатів, на кожному кроці можна отримати підказку, а якщо зроблено помилку – то про це можна негайно дізнатися та зробити крок назад.
Існує багато застосунків для судоку, як під windows, так і під android та IOS, які легко знайти за ключовим словом.
Серед windows-застосунків автору найбільш сподобався TheSudoku.com.
Застосунок має п’ять рівнів складності, дуже просте та інтуїтивно зрозуміле меню.
Серед численних застосунків судоку для андроід слід відзначити Enjoy Sudoku, Andoku Sudoku 3 або Logic Wiz Sudoku.
Технічні прийоми розв’язку
Існують численні прийоми, правильне поєднання яких призводить до розв’язку головоломки. Наведемо далі всі базові та деякі просунуті прийоми в порядку зростання складності.
Відкритий (або єдиний) кандидат (або відкрита/єдина цифра). Нехай в деякій клітині після виключення всіх уже визначених кандидатів, які знаходяться з даною клітиною в одному рядку, стовпчику чи блоці, залишається лише один кандидат. Ставимо кандидата, що лишився, в дану клітину. Це найбільш простий та зрозумілий прийом.
Приклад (Рис.1). Відкритим кандидатом є клітина R9C6. Після того, як в цю клітину поставимо значення 8, відкритим кандидатом стає клітина R9C7 з єдино можливим значенням 5.
Прихований кандидат (прихована цифра). Нехай в деякому домі деяка цифра зустрічається лише один раз (хоча в своїй клітині вона може знаходитися серед інших кандидатів), тоді ставимо цю цифру в цю клітину. Це логічно – ця цифра має бути присутня в домі, але в усіх інших клітинах дому її бути не може.
Приклад (Рис. 1). Прихованим кандидатом у 1-му рядку є цифра 8, яка є лише у клітині R1C3. Інший прихований кандидат – 4 в клітині R5C7, при цьому він одночасно є єдиним кандидатом і у своєму рядку, стовпчику та блоці. Є також прихований кандидат 4 в клітині R8C5, який є єдиним в своєму блоці.
Відкрита пара
Нехай в якихось двох клітинах, які знаходяться в спільному домі (тобто рядку, стовпчику або блоці) залишається лише дві цифри, однакові в обох клітинах. Тоді поки що неможливо зробити висновок, яка саме з двох цифр стоїть в якій клітині, але вже можна зробити висновок про те, що цих двох цифр немає в інших клітинах дому, якому вони належать, отже, можна провести виключення. Таке виключення може призвести до того, що з’явиться нова відкрита або прихована цифра. І взагалі, будь-яке виключення спрощує розв’язок головоломки.
Приклад (рис.2).
Помітимо, що в 1-му стовпці (С1) є гола пара 3-4 у клітинах R3C1 та R7C1. Поки що ми не можемо визначити, в якій з цих двох клітин повинна стояти 3, а в якій – 4, проте можна виключити 3 та 4 з інших клітин 1-го стовпця. Це призведе до того, що 8 стає єдиним кандидатом в R2C1, отже R2C1=8, а після виключення 8 з R9C1, маємо, що R9C1=1.
Аналогічним чином, в 9-му стовпці бачимо голу пару 3-4 у 2-му та 7-му рядках. Виключаючи 3 та 4 з інших клітин 9-го стовпчика, спочатку знаходимо, що
R8C9=5, а потім, що R1C9=1.
Прихована пара
Нехай в якихось двох клітинах, які знаходяться в спільному домі (тобто рядку, стовпчику або блоці) є дві цифри, однакові в обох клітинах. Поряд з ними в цих клітинах можуть бути і інші цифри, але дані цифри відсутні в усіх інших клітинах їхнього дому. Тоді ці клітини можуть бути заповнені даними цифрами одним з двох способів (поки що незрозуміло, яким саме), але вже зрозуміло, що інших кандидатів можна видалити з даних клітин.
Приклад (рис.3).
В останньому стовпчику (С9) цифри 4 та 8 присутні лише в клітинах R1C9 та R6C9. Отже, видаляємо інших кандидатів з цих клітин.
У 5-му блоці цифри 1 та 8 присутні лише в клітинах R4C4 та R6C6. Отже, інших кандидатів з цих клітин можна видалити.
Аналогічним чином можна розглядати і приховані трійки, але побачити їх буде значно складніше.
Відкрита трійка. Метод, схожий на відкриту пару. Нехай у деякому домі є три клітини, кожна з яких містить лише кандидатів з деякої підмножини множини з трьох цифр, наприклад, 123-12-13 або 12-13-23, або 123-123-12, тощо. Зрозуміло, що ці три цифри займають дані три клітини, але незрозуміло, яка цифра міститься в якій клітині. При цьому зрозуміло, що ці три цифри відсутні у всіх інших клітинах дому і їх таким чином можна видалити.
Приклад. На рис.4 виділено відкриту трійку 4-8-9, яка одночасно є трійкою і для 7-го блоку і для 2-го стовпця. Після видалення кандидатів утворюються голі клітини R7C1=2 та R6C2=7, а після цього ще й R5C2=5.
Метод виключення. Цифра 1 у 9-му блоці є тільки у 8-му стовпці, отже, видаляємо 1 у клітинах, які належать 8-му стовпцю та 3-му блоку, тобто в клітинах R1C8 та R2C8. Після цього 1 в клітині R1C9 стає голим кандидатом, а після його занесення 1 в клітині R2C1 також стає голим кандидатом одночасно і у 2-му рядку, і у 1-му блоці.
Аналогічним чином, якщо всі представники якоїсь цифри-кандидата деякого рядка/стовпця цілком належать деякому блоку, то цю цифру можна виключити з усіх клітин блоку, що не лежать в даному рядку/стовпці.
Трикутник або Y -крило. Так називається трійка клітин, значення кандидатів в яких мають вид AB,AC та BC, при цьому одна з клітин (центр) бачить обидві інші клітини (крила). Зрозуміло, що існує два способи заповнення цієї трійки клітин. Нехай центр має кандидатів АС, а крила – AB та BC. Зрозуміло, що при будь-якому з двох варіантів заповнення цих клітин одне з крил матиме значення B, отже B можна виключити з усіх клітин, які бачать обидва крила.
Приклад.
Маємо трикутник з трійкою цифр 1,3,5, в якому клітина R1C5 є центром, а R1C1 та R3C6 є крилами. При цьому крила мають спільного кандидата – 1. Помітимо, що клітина R3C1. Можна виключити 1 зі списку кандидатів в цій клітині. Це призводить до того, що цифра 3 в ній стає єдиним кандидатом, а R1C1=1 та R3C4=9, після чого йде “ланцюгова послідовність” заповнення ще декількох клітин методом єдиного кандидата.
Виключення в будь-якому разі. Розглянемо наступний приклад. Тут, на жаль, не спрацьовує жоден з арсеналу вище розглянутих методів. Але звернемо увагу на те, що одночасно декілька клітин містять відкриту пару 7-9. Зрозуміло, що якщо дві такі клітини лежать в спільному домі, то одна з клітин має значення 7, а інша – 9, і поки що не можна визначити, який з двох способів заповнення вибрати. З’єднаємо всі пари клітин 7-9, які бачать одна одну, ребрами. Пофарбуємо ці клітини у два кольори (наприклад, чорний та червоний) так, щоб суміжні клітини мали різний колір. Тоді клітини одного з двох кольорів дорівнюють 7, а іншого – 9. Помітимо, що клітина R8C1 бачить одночасно чорну клітину R8C5 (по рядку) та R7C3 (по блоку), отже R8C1 не може мати значення 7 або 9.
Тоді R8C1=8, після чого R8C9=8 і далі з’ясовується, що R6C8=7, а оскільки R6C8 – червона клітина, то ставимо 7 у всі червоні клітини, отже 9 – у всі чорні, і, таким чином, приклад розв’язується до кінця.
Сергій Доценко, кандидат фіз.-мат. наук, доцент факультету інформаційних технологій КНУ імені Тараса Шевченка
![Вони першими застосували атомну енергію [1]](/images/202607/atom.jpg#joomlaImage://local-images/202607/atom.jpg?width=850&height=587)
Засновник та видавець