Як вирішувати судоку?

Латинський квадрат

У XVIII столітті великий швейцарський математик Леонард Ейлер придумав цікаву числову структуру, названу «латинський квадрат» (Carr # 233- latin), яка стала прообразом нової гри - числового кросворду, що з'явився в США в 70-х роках минулого століття. Особливою популярністю ця гра в ті роки не мала, тому не відповідала динамічному американському менталітету. Однак, потрапивши до Японії через десятиліття, гра здобула величезну популярність і отримала назву «Судоку» (в перекладі з японської дослівно означає «числа-поруч»). Вже з Японії гра стрімко поширилася по всьому світу, склавши серйозну конкуренцію звичайним кросвордам.

Правила гри

Правила гри прості: в класичному варіанті задається матриця розміром 9х9, розділена на 9 блоків розміром 3х3. Частина клітин заздалегідь заповнена цифрами від 1 до 9. Чим менше клітин заздалегідь заповнено, тим вище складність гри. Блоки розміром 3х3, окреслені жирною лінією, я буду називати секторами, ряди клітин, розташованих по горизонталі - рядками, а по вертикалі - стовпцями. Сектора, рядки і стовпці я буду в цілому називати кластерами, а всю вихідну таблицю 9х9 - матрицею. Єдине правило цієї чудової гри полягає в тому, що цифри в кожному кластері матриці не повинні повторюватися.

Мета гри

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

Рішення судоку

Правило №1. Найпростіше і очевидне правило полягає в тому, що якщо в кластері не заповнена 1 осередок, то вона заповнюється числом 45 - S, де S - сума чисел у кластері.

Правило №2. Припустимо, що ми достовірно знаємо, що число N може бути тільки в двох незаповнених комірках кластеру. У цьому випадку ці осередки я буду називати полузаполненнимі. Якщо тільки в цих же двох осередках кластера може бути також число M, то ці осередки слід вважати заповненими. Отже, два осередки, полузаполненние двома цифрами, є заповненими. Іншими словами, в них не може бути ніяких інших цифр.

З цього простого і очевидного правила є цікава наслідок: якщо в кластері не заповнені 3 осередки, але дві з них полузаполненни числами N і M, то в третьому осередку повинно знаходитися число 45 - N - M - S, де S - сума заповнених цифр в кластері. Це наслідок поширюється на будь-яке число пар полузаполненних осередків.

Правило №2А. Припустимо, що ми достовірно знаємо, що число N може бути тільки в трьох незаповнених комірках кластеру. У цьому випадку ці осередки я буду називати заповненими на 1/3. Якщо тільки в цих же трьох осередках кластера можуть бути також числа M і L, то ці осередки слід вважати заповненими. Отже, три осередки, заповнені на 1/3 трьома цифрами, є заповненими. Іншими словами, в них не може бути ніяких інших цифр.

Продовжуючи по індукції, отримуємо аналогічне правило для чотирьох, п'яти і т.д. осередків.

Правило №3. Два кластери, які мають спільні осередки, я буду називати сполученими. Якщо один з сполучених кластерів - сектор, а інший - стовпець або рядок, то перетин становить три осередки, якщо стовпець і терміну, то одну. Якщо в перетині сполучених кластерів зустрічається число N, то воно не може бути в непересічних частинах обох кластерів.

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

З цього слідства отримуємо ще одне правило:

Правило №4. Всю матрицю можна розділити по горизонталі і по вертикалі на 3 рівних частини (третини) по три рядки або три стовпці. У кожній з цих частин кожне число зустрічається тричі: по одному разу в кожному рядку (стовпці), і в кожному секторі. Якщо число N в якій-небудь третини зустрічається двічі, то третє число повинне знаходитися на перетині тієї рядки (шпальти) і того сектора, в яких це число не зустрічається.

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

Приклад: нехай одна з горизонтальних третин матриці заповнена наступним чином:

2.х.х.х.х.х.х.х.х

Х.х.х.х.2? .2? .х.х.х

Х.х.х.х.х.х.z.z.z

Де х і z - незаповнені клітинки, а 2? - Осередки, полузаполненние числом 2.

Тоді перетин нижнього рядка з останнім сектором (клітини позначені літерою z) повинні бути на 1/3 заповнені числом 2.

Поєднуючи правило №4 для горизонтальних і вертикальних третин матриці, ми можемо однозначно розставити числа в секторі їх перетину. Це і є основне правило вирішення судоку, яке дозволяє вирішити завдання будь-якого рівня складності.

Отже, у вас тепер в руках є все, що вам потрібно для цієї захоплюючої та розвиваючої логічне мислення гри!

Ресурси судоку

Судоку онлайн.

Судоку оффлайн.

Клуб любителів судоку

Грайте на здоров'я! ]