Як розгадувати дуже складні судоку. Логічні головоломки


У цій статті докладно розглянемо яким чином вирішувати складні судоку на прикладі діагонального судоку.

Нам випадає умова номер 437, що показано малюнку 1. І відразу впадає у вічі перший квадрат, він самий насичений на відкриті цифри. Бракує цифр 1, 3,4,9. Але так як горизонталь а трійку містить, то цифра три ставиться на с1. Інші ми точно поставити не можемо. Тому розглянемо, що в нас ще є. Наприклад вертикаль 4 і тут цифра чотири може стояти тільки на b4, через наявність четвірки в п'ятому квадраті і на горизонталь с. Решту цифр ми поки ставити не будемо.

Всі прийоми та методи, які ми застосовуватимемо далі відносяться як до вирішення простих, так і складних судоку.

А що у нас на горизонталі? Тут не вистачає трійки і вона може стояти тільки на b8. (У другому квадраті вона вже є на вертикалі 9). І якщо уважно розглянути далі горизонталь b, то ми виявимо, що у нас є прихована одиначка – цифра 9 на клітці b9. Тому що решта кандидатів (це 1 і 5) на цій клітці стояти не можуть!

Що ми можемо зробити далі? Якщо розглянути п'ять квадратів. Тут цифри 3 і п'яти можуть бути або на d5 або e6. Отже для решти цифр ці клітини не розглядаємо. Тому для одиниці залишається тільки одне місце - клітина d6.

Результат наших дій малюнку 2. Завдяки проведеному нами аналізу ряд b проставляється повністю. Одиниця на b5, п'ятірка на b6. Що дає нам право розставити 3 та 5 у п'ятому квадраті!

Продовжимо аналіз п'ятого квадрата. У ньому не вистачає цифри 7, її немає на головних діагоналях, а що найцікавіше на вертикалі 4. Завдяки цій самій вертикалі ми можемо точно сказати що цифра сім у п'ятому квадраті може стояти або на f4 або e4. Оскільки горизонталі з і d сімку вже містять. А на е5 вона не може стояти з-за вертикалі 4. Далі звернемося до головних горизонталів. І тут сімки відразу розставляються! На i9 та f4.

Що у нас вийшло можна побачити на малюнку 3. Далі будемо продавати аналіз основних діагоналей. Якщо розглянути а1, що йде з клітини, то в ній не вистачає двійки, яка ставиться тільки на h8. Ще в цій діагоналі не вистачає 1, 8 та 9 . Одиночка може стояти тільки на а1, ставимо швиденько її! А вісімка на d4 стояти не може, тому що вона є на горизонталі d вже. Розставляємо - d4-9, e5-8.

А ось тепер ми можемо повністю заповнити п'ятий та перший квадрати! Що в нас вийшло дивимось на малюнку 4.

Зверніть увагу на вертикаль 3. Тут потрібно розставити 1, 6, 7. Одиниця ставиться тільки на f3, а тому розставляються інші - e3 -7, h3-6. Далі на черзі ми маємо вертикаль 9, тому що вона розставляється просто казково. d9-2, g9-6, h9-8.

А якщо нам перевірити на відкриті одинаки?! Наприклад, цифра три сміливо ставиться на клітини d2 та h5. Хоча подальший аналіз одинаків нічого не дає. Тоді звернемося до діагоналі, що залишилася. У неї не вистачає 6, 2, 4. Цифра шість може бути лише на c7. Решту вже просто заповнити.

А чому у нас вертикаль 4 не проставлена ​​до кінця? Виправляємо. с4 -8.

Результат наших досліджень на рисунку5. А тепер заповнимо горизонталь с. с8-1, с5-9, с6-2. І це все, виходячи з наявності цих цифр в інших вертикалях. Грунтуючись на горизонталі з легко заповнити горизонталь d. d1-6, d7-4. Далі просто заповнюється третій квадрат. А ось другий квадрат поки не заповниться, хоча так само лише два кандидати – шістка та сімка. Але по вертикалях п'ять і шість вони не зустрічаються і тому поки що відкладемо їх.

Проаналізувавши всі вертикалі та горизонталі ми приходимо до висновку, що однозначно поставити не можна жодної цифри. Тому переходимо до розгляду квадратів. Звернемося до шостого квадрата. Тут бракує 5,6,8,9. Але цифри 6 і 8 ми можемо точно поставити на клітини f7 і f8. Завдяки нашому аналізу, горизонталь f проставляється вся! f1-9, f2-5. І що ми тут бачимо – четвертий квадрат заповнюється весь! е1-4, е2-2.

Що в нас вийшло, можна подивитися на малюнку 6. Тепер звернемося до квадрата дев'ять. Тут у нас з'являється одна відкрита одинак ​​- цифра один на i7. Завдяки чому ми можемо поставити один у сьомому квадраті на g2. Вісімка на i2.

Багатьом подобається змушувати себе думати: комусь – для розвитку інтелекту, комусь – для підтримки своїх мізків у добрій формі (так-так, не тільки тілу потрібна зарядка), та найкращим тренажеромдля розуму є різні ігри на логіку та головоломки. Одним з варіантів подібних розваг, що розвивають, можна назвати судоку. Проте деякі й не чули про таку гру, що вже говорити про знання правил чи інші цікаві моменти. Завдяки статті ви дізнаєтеся про всю необхідну інформацію, наприклад, як розгадати судоку, а також їхні правила та види.

Загальне

Судоку – це головоломка. Іноді складна, важко розкривається, але завжди цікава і затягує будь-яку людину, яка зважилася на цю гру. Назва походить від японської: «су» означає «цифра», а «доку» - це «стояча окремо».

Не всі знають як розгадувати судоку. Складні головоломки, наприклад, під силу або розумним новачкам, які добре розуміють, або професіоналам своєї справи, що практикують гру не один день. Просто так взяти і за п'ять хвилин вирішити поставлене завдання далеко не кожному можливо.

Правила

Отже, як розгадувати судоку. Правила дуже прості та зрозумілі, запам'ятати їх легко. Однак не думайте, що нескладні правила обіцяють «безболісне» рішення; думати доведеться багато, застосовувати логічне і стратегічне мислення, прагнути відтворити картину Напевно, треба любити цифри, щоби розгадувати судоку.

Спочатку креслиться квадрат 9 х 9 клітин. Потім жирнішими лініями він поділяється на так звані «регіони» по три квадратики в кожному. У результаті виходить 81 клітина, яка зрештою має бути повністю заповнена числами. У цьому полягає складність: розставлені по всьому периметру цифри від 1 до 9 нічого не винні повторюватися ні в «регіонах» (квадратах 3 х 3), ні лініях по вертикалі і/або горизонталі. У будь-якому судоку спочатку є деякі заповнені клітини. Без цього гра просто неможлива, оскільки інакше вийде не розгадування, а вигадування. Кількість цифр залежить від складності головоломки. Складні судоку містять трохи чисел, розставлених часто так, що доведеться добряче поламати голову, перш ніж вирішити їх. У легеньких - близько половини цифр уже стоять на своїх місцях, завдяки чому розгадати стає в рази простіше.

Повністю розібраний приклад

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

Спочатку можна подивитися на лінії або квадрати, де особливо багато цифр. Наприклад, чудово підходить другий стовпець зліва, там не вистачає лише двох чисел. Якщо подивитися на ті, що вже є, стає очевидно, що не вистачає 5 і 9 у клітинах, що порожніють, на другому і восьмому рядках. З п'ятіркою поки не все ясно, вона може бути і там, і там, але якщо поглянути на дев'ятку – все зрозуміло. Так як на другому рядку вже є цифра 9 (у сьомому стовпці), значить, щоб не було повторів, дев'ятку потрібно поставити вниз, на 8 рядок. Методом виключення додаємо 5 на 2-й рядок – і ось у нас вже є один заповнений стовпець.

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

Цього разу візьмемо за основу середній «регіон», у якому не вистачає п'яти цифр: 3, 5, 6, 7, 8. Кожну клітинку ми заповнюємо не більшими результативними числами, а маленькими, «чорновими». Просто пишемо в кожен квадратик ті цифри, яких не вистачає і які можуть бути там через їхню нестачу. У верхній клітині це 5, 6, 7 (3 на цьому рядку вже є в регіоні праворуч, а 8 - зліва); у клітині зліва можуть бути 5, 6, 7; у самій середині - 5, 6, 7; справа – 5, 7, 8; знизу – 3, 5, 6.

Отже, тепер дивимося, які міні-цифри містять відмінні від інших цифр. 3: є лише одному місці, в інших її немає. Значить, її можна виправляти на велику. 5, 6 і 7 є як мінімум у двох клітинах, отже, даємо їм спокій. 8 є тільки в одній, отже, решта цифр відпадає і можна залишати вісімку.

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

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

От і все; готовий результат:

Види

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

Висновок

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

Всім привіт! У цій статті докладно розберемо рішення складних судок на конкретному прикладі. Перед початком розбору умовимося називати малі квадрати цифрами, нумеруючи їх ліворуч і зверху вниз. Усі основні засади рішення судоку розписано у цій статті.

Як завжди в першу чергу ми розглянемо відкриті одинаки. І таких виявилося лише дві b5-5, e6-3. Далі розставимо потенційних кандидатів на всі порожні поля.

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

Плід наших праць можна побачити на малюнку 2. Звернемо свою увагу на клітину f2. Вона має двох кандидатів 5 і 9. Нам доведеться піти методом вгадування, і в разі помилки повернутися до цього вибору. Давайте поставимо п'ять цифр. Приберемо п'ятірку з кандидатів рядка f, стовпця 2 та квадрата чотири.

Прибирати можливих кандидатів після проставлення числа ми постійно і в цій статті акцентувати на тому увагу більше не будемо!

Дивимося далі на четвертий квадрат, у нас є трійник – це клітини e1, d2, e3, які мають кандидатів 2, 8 та 9. Приберемо їх із решти незаповнених клітин четвертого квадрата. Йдемо далі. У квадраті шість цифра п'ять може бути лише на е8.

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

І так на другій вертикалі цифра 8 може бути тільки на клітинах -h2 та i2, заберемо вісімку з інших незаповнених клітин сьомого квадрата. На третій вертикалі цифра вісім може перебувати лише на е3. Що в нас вийшло дивимось на малюнку 3.

Далі нічого за що можна зачепитися знайти не вдається. Нам попався досить міцний горішок, але ми його все одно розкусимо! Отже, розглянемо знову нашу пару е1 і d2, розставимо її в такий спосіб d2-9, e1 -2. І у разі нашої помилки повернемося знову до цієї пари.

Тепер у клітинку d9 сміливо можемо записати двійку! А у квадраті сім, дев'ятка може бути лише на h1. Після чого на вертикалі 1 п'ятірка може бути тільки на i1, що дає право на клітину h9 поставити п'ятірку.

На малюнку 4 зображено, що ми вийшло. Тепер розглянемо наступну пару, це d3 та f1. У них кандидати 7 і 6. Забігаючи наперед скажу, що варіант розміщення d3-7, f1 -6 помилковий і ми його розглядати в статті не будемо, щоб не гаяти час.

Малюнок 5 ілюструє нашу працю. Що нам залишається робити далі? Звичайно, знову перебирати варіанти проставлення цифр! Ставимо у клітину g1 трійку. Як завжди, зберігаємося, щоб можна було повернутися. На i3 ставиться одиниця. тепер у сьомому квадраті ми отримуємо пару h2 та i2, з цифрами 2 та 8. Це дає нам право виключити ці цифри з кандидатів по всій незаповненій вертикалі.

Виходячи з останньої тези, розставляємо. а2-четвірка, b2 - трійка. І після цього ми можемо проставити весь перший квадрат. с1 -шістка, а1 - одиниця, b3 - дев'ятка, с3 - двійка.

На малюнку 6 показано, що вийшло. На i5 у нас прихована одиначка – цифра три! А на i2 може стояти лише цифра 2! Відповідно, на h2 – 8.

Тепер звернемося до клітин е4 і е7, це пара з кандіатами 4 і 9. Розставимо їх так е4 четвірка, е7 дев'ятка. Тепер на f6 ставиться шістка, а на f5 дев'ятка! Далі на с4 отримуємо приховану одиначку - цифру дев'ять! І одразу можемо проставити з 8 чотири, а потім закрити горизонталь з: с6 вісімка.

ВКонтакте Facebook Однокласники

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

Але для тих, кому розгадування судоку коштує надто великих зусиль, це може бути ідеальним рішенням.

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

Дослідники комплексних мереж Золтан Торожкай та Марія Ерксі-Раваз з Університету Нотр-Дама також змогли пояснити, чому деякі загадки судоку складніші за інші. Єдиний недолік у тому, що для того, щоб зрозуміти, що вони пропонують, потрібна ступінь доктора математики.


Чи можете ви вирішити цю головоломку? Вона створена математиком Арто Інкалою, і, як стверджують, це найскладніша судоку у світі. Фото із сайту nature.com

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

Натомість Торожкай та Ерксі-Раваз запропонували універсальний аналоговий алгоритм, який абсолютно детермінований (не використовує припущення чи перебір) і завжди знаходить правильне вирішення завдання, причому досить швидко.


Дослідники використовували "детермінований аналоговий вирішувач", щоб заповнити цю судоку. Фото із сайту nature.com

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

Вони створили шкалу від 1 до 4, де 1 – «легко», 2 – «середній ступінь складності», 3 – «складно», 4 – «дуже складно». Для вирішення головоломки з рейтингом 2 потрібно в середньому в 10 разів більше часу, ніж для задачі з рейтингом 1. Згідно з цією системою, сама складна загадкаіз відомих досі має рейтинг 3.6; Складніші завдання судоку поки невідомі.


Теорія починається з картографії ймовірностей кожного окремого квадрата. Фото із сайту nature.com

«Я не цікавився судоку, поки ми не почали працювати над більш загальним класомздійсненності Булевих проблем, – каже Торожкай. – Оскільки судоку – частина цього класу, латинський квадрат 9-го порядку виявився для нас добрим полем для випробувань, то я з ними й познайомився. Мене та багатьох дослідників, які вивчають такі проблеми, захоплює питання, як далеко ми, люди, здатні зайти у рішенні судоку, детерміновано, без перебору, який є вибором навмання, і, якщо здогад не вірний, потрібно повернутися на крок або на кілька кроків назад та почати спочатку. Наша аналогова модель рішення детермінована: у динаміці немає жодного випадкового вибору чи повернення».


Теорія хаосу: ступінь складності загадок виявляється тут як хаотична динаміка. Фото із сайту nature.com

Торожкай та Ерксі-Раваз вважають, що їхній аналоговий алгоритм потенційно підходить для застосування до рішення великої кількостірізноманітних завдань та проблем у промисловості, інформатиці та обчислювальної біології.

Досвід дослідження також зробив Торіжка великим любителем судоку.

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

Методологія Торожка та Ерксі-Раваз була вперше опублікована в журналі Nature Physics, а потім – у журналі Nature Scientific Reports.

СУДОКУ - це популярна гра- пазл, яка являє собою головоломку з цифрами, здолати яку можна тільки будуючи логічні висновки. У назві Судоку в перекладі з японського "су" - "цифра", а doku "доку" - "стоячи окремо". Отже, «СУДОКУ» у приблизному перекладі означає «одиночна цифра».

Назва "Sudoku" дало цій головоломці японське видавництво Nicoli у 1984 році. Sudoku - це скорочення від "Suuji wa dokushin ni kagiru", що в перекладі з японської означає "число має бути єдиним". Видавництво Nikoli не лише придумало звучне ім'я, а й уперше запровадило симетрію у завданнях для своїх головоломок. Назву головоломці дав керівник Nicoli - Кaji Maki. Весь світ прийняв цю нову японську назву, але в самій Японії головоломку називають "Nanpure". Nicoli зареєструвало у своїй країні слово "Sudoku" як торгову марку.

Історія походження СУДОКУ

Батьківщиною шахів вважається Індія, батьківщиною футболу – Англія. У гри судоку (sudoku), що швидко поширилася по всьому світу, батьківщини як такої немає. Прообразом судоку можна вважати головоломку "Магічний квадрат", яка з'явилася в Китаї 2000 років тому.

Історія судоку як гри походить від імені знаменитого швейцарського математика, механіка і фізика Леонарда Ейлера (1707 - 1783).

У паперах його архіву, датованих 17 жовтня 1776 року, містяться записи про те, як утворити магічний квадрат з певним числом осередків, особливо 9, 16, 25 і 36. Наукове дослідженнянових різновидів магічного квадрата» Ейлер поміщав у клітини латинські літери (Латинський квадрат), пізніше заповнив клітини грецькими літерами і називав квадрат греко-латинським. Досліджуючи різні варіантиМагічний квадрат, Ейлер звернув увагу на проблему комбінації символів таким чином, щоб не один з них не повторювався в жодному рядку і в жодному стовпці.

У сучасному виглядіголоволомки судоку вперше були опубліковані у 1979 році в журналі Word Games magazine. Автором головоломки був Гарвард Гаріс з Індіани. Головоломку «Number Place» (у перекладі російською - "місце числа") - це можна вважати одним з перших випусків сучасних судок. У ній було додано блоки розміром 3х3 клітини, що було важливим удосконаленням, оскільки дозволило зробити головоломку цікавішою. Він використав принцип латинського квадрата Ейлера, застосував його в матриці розмірністю 9х9 і додав додаткові обмеження, цифри не повинні повторюватись і у внутрішніх квадратах 3х3.

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

У Японії ця головоломка була опублікована компанією Nicoly Inc., великим видавцем збірок різних головоломок, у газеті Monthly Nicolist у квітні 1984 року під заголовком «Кількість може використовуватися лише один раз». 12 листопада 2004 року газета The Times вперше на своїх сторінках опублікувала головоломку судоку. Ця публікація стала сенсацією, головоломка швидко поширилася по всій Британії, Австралії, Новій Зеландії; набула популярності і в США.

Варіанти судоку

Отже, що ж являє собою судоку? В даний час з'явилося безліч модернізацій для цього популярного виду головоломок, але класична судоку є квадратом 9х9 клітин, розбитий на підквадрати зі сторонами по 3 клітини кожен. Таким чином, загальне ігрове поле становить 81 клітину. У додатку до моєї роботи я поміщу різні видисудоку та варіанти рішень (їх мені допомагали вирішити батьки).

Судоку різняться за рівнем складності залежно від розміру квадрата:

  • 1. Для маленьких любителів головоломок робляться судоку з полями 2х2, 6х6 клітини.
  • 2. Для професіоналів існують судоку 15х15 та 16х16 клітин

Судоку бувають різних рівнів:

  • легкий
  • середній
  • складний
  • дуже складний
  • суперскладний

Правила вирішення

У головоломок судоку лише одне правило. Необхідно заповнити вільні клітини так, щоб у кожному рядку, у кожному стовпці та у кожному малому квадраті 3Х3 кожна цифра від 1 до 9 зустрічалася б лише 1 раз. Частина клітин у судоку вже заповнена цифрами і вам залишається заповнити інші. Чим більше цифр стоїть спочатку, тим простіше вирішити головоломку. До речі, правильно складена судоку має лише одне рішення.

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

Стратегія рішення судоку включає три етапи:

  • вивчення розташування цифр у головоломці
  • попереднє розміщення цифр
  • аналіз

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

Математична основа. Кількість можливих комбінацій у судоку 9x9 становить за розрахунками Бертхама Фельгенхауера 6670903752021072936960.