Як вирішувати судоку, Світ навколо нас
У XVIII столітті великий швейцарський математик Леонард Ейлер вигадав цікаву числову структуру, названу «латинський квадрат» (Carré 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 для горизонтальних і вертикальних третин матриці, ми можемо однозначно розставити числа в секторі їх перетину.Це і є основне правило рішення судоку, яке дозволяє вирішити завдання будь-якого рівня складності.
Отже, у вас тепер в руках є все, що вам знадобиться для цієї захоплюючої гри, що розвиває логічне мислення!