Как решать задания в КУЛ (часть 3)
Константин Дудин
Навигация:
Как решать СУДОКУ
Судоку
Судоку – японская головоломка, в которой нужно вписывать цифры по определенному алгоритму (так, чтобы они не повторялись по вертикали и горизонтали).
Игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась только один раз.
Сложность судоку зависит от количества изначально заполненных клеток и методов, которые нужно применять для её решения. Самые простые решаются дедуктивно: всегда есть хотя бы одна клетка, куда подходит только одно число. Некоторые головоломки можно решить за несколько минут, на другие можно потратить несколько часов
Существует несколько способов решения судоку. Вот некоторые из них:
Классический способ с перебором. Подходит для решения судоку любой сложности. Лучше всего сработает на простых игровых полях, где изначально цифрами заполнена минимум половина ячеек.
Последовательный способ. В каждую пустую ячейку впишите все цифры от 1 до 9, а затем просто вычёркивайте неподходящие.
Метод исключения. Этот способ позволяет очень быстро заполнять пустые клетки, но подойдёт только самым внимательным.
Анализ малых квадратов. Рассмотрите каждый малый квадрат и выпишите рядом с ним все цифры, которых в нём не хватает.
Разновидности судоку:
Классический судоку
Символьный судоку - вместо цифр в клеточках стоят 9 разных символов. Суть игры та же, что и у классического судоку - символы не должны повторяться по вертикали, горизонтали и малом квадрате
Цветной судоку - вместо цифр в клеточках стоят цвета. Суть решения та же что и у классического, с той лишь разницей, что под квадратом стоят цвета с цифрами, обозначающими их кол-во в данном судоку
Сумсудоку (также известен как "убийца судоку") - это сочетание судоку и какуро. Как правило, разгадывать данные головоломки легче чем обычные судоку. Кроме обычных правил судоку (в столбцах, строках и больших квадратах не должно быть одинаковых чисел), добавляются также области, обозначенные пунктиром, внутри которых сумма всех чисел должна быть равна указанному значению.
Числовой судоку - подобном судоку сначала нужно решить примеры, а затем найти полученные произведения в таблице. Ответы могут быть приведены в прямом или обратном порядке, расположены в горизонтальном, вертикальном или диагональном направлении, но обязательно по прямой и без разрывов.
Диагональный судоку - В этом типе судоку уникальность чисел должна также соблюдаться и по диагонали
Виндоку - судоку с дополнительными 4-мя квадратам, в которых должна соблюдаться уникальность чисел
Как решать
Рассмотрим на примере, как решать судоку
В первую очередь стоит проверить строки, столбцы или квадраты, где присутствует наибольшее кол-во известных чисел. В данном примере это средний столбец. Здесь не хватает цифр 5 и 8. В верхнем квадрате уже есть цифра 8, следуя правилу уникальности чисел в каждом квадрате, горизонтальной линии и вертикальном столбце, 8 нужно ставить в нижний квадрат. Следовательно в верхнем квадрате будет стоять 5.
Далее рассмотрим малые квадраты в среднем столбце. В каждом из них должны быть цифры от 1 до 9. В верхнем нет цифр 2, 4, 7, в среднем – 2, 6, 8, 9, в нижнем – 1, 4, 9.
Начнем по порядку: 1-у в нижнем квадрате ставим в 4-й столбец, потому что во 5-ом и 6-ем она уже есть в квадратах ниже. 2-у и 4-у мы пока не знаем куда подставить, поэтому пока откладываем их. 7 есть в нижнем и среднем квадрате, значит она может стоять в одном из ячеек 4-го столбца – запоминаем (или же вы можете пометить для себя карандашом). 8 ставим в 6-ой столбец среднего квадрата, 9 пока откладываем.
Теперь, когда мы подставили первые несколько чисел, можем посмотреть, каких цифр в принципе больше всего. Т.е. у нас есть: 1 – 6 шт, 2 – 1 шт., 3 – 3 шт. и т.д. После этого мы можем попытаться найти числа с наибольшим кол-вом. Например, у нас есть 6 шт. 1 и 8, и 7шт. 5. Давайте посмотрим, которые из них мы можем подставить.
И видим в правых малых квадратах отсутствует 8 в 7 столбце, тогда как в 1 и 2 горизонтальных строчках также присутствуют 8-и. Так что смело можем подставлять еще одну 8. Точно также находим 1 и 5 в малых квадратах слева и справа.
Далее проверяем остальные числа. Из двоек нам известны лишь одна, поэтому пока их не трогаем.
Можно подставить 3 в средний малый квадрат справа, а в верхнем видно, что тройка может стоять в двух местах - запоминаем.
Таким же образом мы можем отметить для себя и остальные числа, которые позже позволят быстрее определить определить числа, которые могут стоять в ячейке. Например, в 6-ой горизонтальной линии нам известны какие и где примерно стоят числа. И стоит вам найти одно из них (например 9), как тут же будут расставлены по своим местам и остальные.
Также такой способ отметок может подсказать нам расположение других чисел. Например, мы видим, что в 9 столбце в верхнем малом квадрате стоят тройки, а значит их нет в малом нижнем квадрате. Это знание позволяет нам определить расположение 3, так она у нас уже есть в 9-ой горизонтальной строчке и 7-ом столбце. Тут же можно пометить расположение 3 в малом нижнем квадрате слева.
Таким образом находим все остальные цифры.
Во 2-ой горизонтальной линии мы видим, что 3 квадрате 7-и стоят только в двух ячейках. Их расположение позволяет определить положение 7 и 4 в среднем верхнем квадрате.
Продолжаем поиски, проверяя каждый малый квадрат и отмечая возможные варианты чисел. В простых уровнях цифры постепенно встают на свои места. Но в более сложных зачастую приходишь к моменту, когда найдены все возможные цифры и остаются лишь предполагаемые числа, как показано на рисунке ниже. На данном этапе стоит быть очень внимательным и подставлять цифры, используя метод подбора. Если вы в какой-то момент заметить, что числа не сходятся, значит стоит сделать несколько шагов назад и подставить уже другие числа.
Попробуем в 6 строчке расположить цифры в таком порядке: 2 9 4. Смотрим, что получается:
Мы дошли до момента, когда надо еще раз подставить одно из возможных чисел. В этот раз расставим числа в правом верхнем квадрате.