Японские головоломки СУДОКУ

Судоку

Судоку - это логическая головоломка с числами, которая приобрела большую популярность в последнее время. В переводе с японского су - цифра, доку - стоящая отдельно. Игровое поле представляет собой квадрат размером 9x9 клеток, таким образом всего клеток - 81. В некоторых из них в начале игры стоят некоторые числа (от 1 до 9). В зависимости от того, сколько клеток заполнено, конкретный кроссворд судоку относится к простым или сложным. Решением судоку является постепенное заполнение игрового поля цифрами, в соответствии с правилами.

НЕМНОГО ИСТОРИИ

У популярной головоломки судоку (sudoku) определенной родины нет. Многие считают, что судоку является японским развлечением, но на самом деле Япония может считаться только родиной названия.

 Прародителем судоку можно считать головоломку "Магический квадрат", которая была известна еще в древнем Китае около 2000 лет назад. Игра представляла собой квадрат размером 3х3 клетки. В каждую клетку вписывалось одно число от 1 до 9. В Европе история судоку приводит к имени знаменитого швейцарского математика, и физика Леонарда Эйлера (1707 - 1783). 

В документе, озаглавленном "Научное исследование новых разновидностей магического квадрата" Эйлер помещал в клетки латинские буквы (получая Латинский квадрат), позже он заполнил клетки греческими буквами и называл квадрат греко-латинским. Исследуя различные варианты магического квадрата, Эйлер обратил внимание на проблему комбинации символов так, чтобы ни один из них не повторялся ни в одной строке и ни в одном столбце. С помощью своих исследований он выяснил, что в матрице размером 9х9 каждый ряд и каждую колонку можно заполнить цифрами от 1 до 9 в определенном порядке и без повторения.

Далее головоломка судоку продолжала своё развитие. И в 1979 году Howard Garns из Индианы публикует в "Dell Magazines" головоломку "Number Place" - это можно считать одним из первых выпусков современных судоку. В Японии эта головоломка была опубликована компанией Nicoly Inc., одним из крупных издателей сборников головоломок, в газете Monthly Nicolist в апреле 1984 года под заголовком "Число может использоваться только один раз". 

Название головоломке придумал руководитель Nicoli - Кaji Maki. В названии Sudoku Su - обозначает число, а doku - единственное. В конце 2004 года британская "Times" стала печатать судоку на своих страницах, чем прославила эту головоломку на всю Европу. Эта публикация принесла судоку большую популярость, головоломка быстро распространилась по всей Британии, Австралии, США.
В настоящее время выдается множество специализированных журналов, книг и инструкций по решению судоку. Много газет печатают эти головоломки вместе с кроссвордами и другими логическими задачами. Не меньшую популярность завоевали судоку и в сети Интернет, судоку онлайн пользуются большой популярностью среди пользователей всемирной паутины.
Правила решения судоку 

В судоку играют на поле размером 9х9 клеток, которое изначально заполнено некоторым количеством цифр от 1 до 9.
Целью игры судоку является  заполнение пустых клеток игрового поля цифрами от 1 до 9, используя уже вписанные цифры. Цифры должны быть расположены таким образом, чтобы по всем столбцам, строкам, а также внутри каждой области 3х3 клетки на игровом поле судоку цифры не повторялись.
Начинать заполнять игровое поле судоку лучше с тех столбцов, строк или областей 3х3 клетки, где известно максимальное количество цифр. Прежде чем вписать число в клетку игрового
поля судоку, проверьте соответствующие строку, столбец и область 3х3, не записана ли в них эта цифра. Если выбранная цифра не повторяется и на этом месте не может быть другой цифры - заполняйте клетку. Используя метод подбора цифр Вы сможете заполнить  всё игровое поле судоку.
Чтобы записать цифру в клетку игрового поля, сначала необходимо выбрать ее из стобца с цифрами справа от игрового поля, кликнув по необходимой цифре мышкой. Напротив выбранной цифры появится указатель, показывающий, что цифра является активной.
Далее кликом по пустой клетке игрового поля судоку Вы можете записать цифру в клетку. Чтобы убрать ошибочную цифру кликните по ней еще раз



Базовые методы решения судоку

1. Основы


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



1.1 «Последний герой»

Рассмотрим седьмой квадрат. Всего четыре свободных клетки, значит что-то можно быстро заполнить.
"8" на D3 блокирует заполнение H3 и J3; точно также "8" на G5 закрывает G1 иG2
С чистой совестью ставим "8" на H1












1.2 «Последний герой» в строке

После просмотра квадратов на очевидные решения, переходим к столбцам и строкам.
Рассмотрим "4" на поле. Понятно, что она будет где-то в строке A.
У нас есть "4" на G3, что зыкрывает A3, есть "4" на F7, убирающая A7. И ещё одна "4" во втором квадрате запрещает её повтор на A4 и A6.
«Последний герой» для нашей "4" это A2









1.3 «Выбора нет»

Иногда есть несколько причин для конкретного расположения. "4" в J8 будет отличным примером.
Синие стрелки показывают, что это последнее возможное число в квадрате.Красные и синие стрелки дают нам последнее число в столбце 8Зеленыестрелки дают последнее возможное число в строке J.
Как видим, выбора у нас нет, кроме как поставить эту "4" на место. 






1.4 «А кто, как не я?»

Заполнение чисел проще проводить вышеописанными методами. Однако проверка числа, как последнего возможного значения, тоже даёт результаты. Метод стоит применять, когда кажется, что все числа есть, но чего-то не хватает.
"5" в B1 ставится исходя из того, что все числа от "1" до "9", кроме "5" есть в строке, столбце и квадрате (отмечено зеленым).

На жаргоне это "Голая одиночка". Если заполнять поле возможными значениями (кандидатами), то в ячейке такое число будет единственным возможным. Развивая эту методику, можно искать "Скрытые одиночки" — числа, уникальные для конкретной строки, столбца или квадрата.

2. «Голая миля»




2.1 «Голые» пары


"«Голая» пара" — набор из двух кандидатов, расположенных в двух ячейках, принадлежащих одному общему блоку: строке, столбцу, квадрату.
Понятно, что правильные решения головоломки будут только в этих ячейках и только с этими значениями, в то время как все другие кандидаты из общего блока могут быть убраны.
В этом примере несколько «голых пар».
Красным в строке А выделены ячейки А2 и А3, обе содержащие "1" и "6". Я пока не знаю, как именно они расположены здесь, но я спокойно могу убрать все другие "1" и "6" из строки A (отмечено желтым). Также А2 и А3 принадлежат общему квадрату, поэтому убираем "1" из C1.



2.2 «Threesome»

«Голые тройки» — усложненный вариант «голых пар».
Любая группа из трех ячеек в одном блоке содержащая в общем три кандидата является «голой тройкой». Когда такая группа нашлась, эти три кандидата могут быть убраны из других ячеек блока.

Комбинации кандидатов для «голой тройки» могуть быть такими:

[abc] [abc] [abc] // три числа в трех ячейках.
[abc] [abc] [ab] // любые комбинации.
[abc] [ab] [ab] // любые комбинации.
[ab] [aс] [bc] 
В этом примере все довольно очевидно. В пятом квадрате ячейки E4E5E6содержат [5,8,9], [5,8], [5,9] соответственно. Получается, что в общем у этих трех ячеек есть [5,8,9], и только эти числа там могут быть. Это позволяет нам убрать их из других кандидатов блока. Этот трюк даёт нам решение "3" для ячейки E7.



2.3 «Великолепная четверка»


"«Голая» четверка" весьма редкое явление, особенно в полной форме, и все же дает результаты при обнаружении. Логика решения такая же как и у«голых троек»
В указанном примере в первом квадрате ячейки A1B1B2 и C1 в общем содержат [1,5,6,8], поэтому эти числа займут только эти ячейки и никакие другие. Убираем подсвеченных желтым кандидатов.








3. «Все тайное становится явным»




3.1 Скрытые пары

Отличным способом раскрыть поле будет поиск скрытых пар. Этот метод позволяет убрать лишних кандидатов из ячейки и дать развитие более интересным стратегиям.
В этой головоломке мы видим, что 6 и 7 есть в первом и втором квадратах. Кроме этого 6 и 7 есть в столбце 7. Комбинируя эти условия, мы можем утверждать, что в ячейках A8 и A9 будут только эти значения и все другие кандидаты мы убираем.










Более интересный и сложный пример скрытых пар. Синим выделена пара [2,4] вD3 и E3, убирающая 3, 567 из этих ячеек. Красным выделены две скрытые пары, состоящие из [3,7]. C одной стороны, они уникальны для для двух ячеек в7 столбце, с другой стороны — для строки E. Выделеные желтым кандидаты убираются. 








3.1 Скрытые тройки

Мы можем развить скрытые пары до скрытых троек или даже скрытых четверокСкрытая тройка состоит из трех пар чисел, расположенных в одном блоке. Такие как [a,b,c], [a,b,c] и[a,b,c]. Однако, как и в случае с «голыми тройками», в каждой из трех ячеек не обязательно должно быть по три числа. Сработают всего три числа в трех ячейках. Например [ab], [aс], [bc]. Скрытые тройки будут замаскированы другими кандидатами в ячейках, поэтому сначала надо убедиться, что тройка применима к конкретному блоку.

В этом сложном примере есть две скрытые тройки. Первая, отмеченная красным, в столбце А. Ячейка А4 содержит [2,5,6], A7 — [2,6] и ячейка A9 -[2,5]. Эти три ячейки единственные, где могут быть 2 ,5 или 6, поэтому только они там и будут. Следовательно убираем лишних кандидатов.

Вторая, в столбце 9. [4,7,8] уникальны для ячеек B9C9 и F9. Используя ту же логику, убираем кандидатов.




3.1 Скрытые четверки


Прекрасный пример скрытых четверок. [1,4,6,9] в пятом квадрате могут быть только в четырех ячейках D4D6F4F6. Следуя нашей логике, убираем всеъ других кандидатов (отмеченых желтым).

4. «Нерезиновая»


Если любое из чисел появляется дважды или трижды в одном блоке (строке, столбце, квадрате), тогда мы можем убрать это число из сопряженного блока. Есть четыре вида сопряжения:
  1. Пара или Тройка в квадрате — если они расположены в одной строке, то можно убрать все другие такие же значения из соответствующей строки.
  2. Пара или Тройка в квадрате — если они расположены в одном столбце, то можно убрать все другие такие же значения из соответствующего столбца.
  3. Пара или Тройка в строке — если они расположены в одном квадрате, то можно убрать все другие такие же значения из соответствующего квадрата.
  4. Пара или Тройка в столбце — если они расположены в одном квадрате, то можно убрать все другие такие же значения из соответствующего квадрата.




4.1 Указавающие пары, тройки


В качестве примера покажу эту головоломку. В третьем квадрате "3" находится только в B7 и B9. Следуя утверждению N1, мы убираем кандидатов из B1B2,B3. Аналогично, "2" из восьмого квадрата убирает возможное значение из G2.










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











4.2 Сокращаем несокращаемое

Эта стратегия включает в себя аккуратный анализ и сравнение строк и столбцов с содержимым квадратов (правила N3N4).
Рассмотрим строку А. "2" возможны только в А4 и А5. Следуя правилу N3, убираем "2" их B5C4C5.












Продолжим решать головоломку. Имеем единственное расположение "4" в пределах одного квадрата в столбце. Согласно правилу N4, убираем лишних кандитатов и, в добавок, получаем решение "2" для C7.










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



Предлагаю решить  







Комментариев нет:

Отправить комментарий