Menu GrandGames.net
Русский РусскийEnglish English
RU
VKFB LoginРегистрацияNewsЛента

Информация - Инструкция по решению судоку от alex_tlt

Головоломки> Информация > Инструкция по решению судоку от alex_tlt (2016-02-29)

Данный алгоритм по решению судоку 9x9 прислал наш регулярный игрок Александр Кузнецов (alex_tlt)

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

Моя цель – показать алгоритм, то есть, последовательность действий, которая обязательно приведёт к успеху.

В качестве примера используется судоку № 3448. Алгоритм состоит из четырёх пунктов.

  1. Поиск единственной пустой клетки в строке, столбце, квадрате.
  2. Поиск единственной выбранной цифры в квадрате.
  3. Поиск единственно допустимого варианта из оставшихся в строке, столбце, квадрате (последний кандидат).
  4. Решение альтернатив.

1. Если в строке, столбце или квадрате заполнены 8 клеток, то в девятую, пустую клетку надо вписать недостающую цифру. Если при этом окажется, что в большом квадрате 9х9 пустых клеток не осталось, судоку считается решенным. Этот пункт не требует иллюстраций, его я включил только лишь для соблюдения полноты алгоритма.

2. Квадрат выгодно отличается от строк и столбцов своей компактностью. Поэтому целесообразно начинать решение именно с квадратов. Выбираем любую цифру от 1 до 9 и мысленно проецируем заполненные цифры на те квадраты, в которых выбранной цифры нет. Предпочтительнее начинать с самой часто встречающейся в условии цифры. Если же не учитывать этот фактор, начинаем с цифры 1.

Четыре единицы (они выделены фоном) проецируются на 5 квадратов, не содержащих эту цифру. Сразу же обнаруживаются единственные пустые клетки в среднем квадрате и нижнем правом квадрате.

Заполняем эти клетки единицами:

Продолжаем поиск в оставшихся квадратах цифры 1 с учётом найденных.

Новых единиц не найдено. Переходим к следующей цифре 2, будет найдена одна двойка. Рисунок не привожу, чтобы не загромождать документ. Переходим к следующим цифрам, будут найдены тройка, пятёрка, семёрки. Что касается восьмёрок, иллюстрация просто необходима!

Четыре восьмёрки проецируются на 5 квадратов, не содержащих эту цифру. Единственные пустые клетки обнаруживаются в нижнем среднем квадрате и в среднем левом. Причём последний – совершенно пуст! Это ещё раз подчёркивает высказанное ранее положение о компактности квадратов. В нашем случае достаточным оказалось четыре цифры, чтобы закрыть восемь пустых клеток.

Далее, после поиска цифры 9 судоку приобретает следующий вид:

Теперь необходимо применить пункт 1 (его всегда нужно держать в уме) последовательно для самой нижней строки, где недостаёт шестёрки, а затем для нижнего левого квадрата, где недостаёт семёрки.

Возвращаемся к пункту 2 и возобновляем поиск с цифры 1. В данном алгоритме пункт 2 должен закончиться только тогда, когда перебор всех 9-ти цифр не даст ни единого положительного решения.

Переходим к пункту 3.

3. В третьей сверху строке остались незаполненными три клетки-кандидата с цифрами 4, 5, 6 (серые цифры). В шестом столбце уже есть 5 и 6, следовательно остается вариант 4 - последний кандидат.

Сложные судоку, как правило, не обходятся без пункта 4 «Альтернативы». Разберём этот случай применительно к судоку № 3448, допустив что на определённом этапе мы не смогли обойтись п.п. 1-3.

4. В самом левом столбце остались незаполненными две клетки, значения которых могут быть либо 1, либо 4, и они отмечены серыми цифрами. В этом случае предполагаем, что 1 находится в верхней клетке и нажимаем кнопку «Сохранить».

После того, как судку сохранен, в альтернативной клетке ставим 4 и выполняем пункт 2 «Поиск по квадратам».

В результате приходим к противоречию: пятая сверху строка содержит две одинаковые цифры 4. Замечу, что при решение альтернатив противоречие является наиболее желаемым результатом! Теперь остаётся нажать кнопку «Загрузить» и в сохранённом судоку в верхней клетке вместо 1 поставить 4, а в альтернативной 1.

А далее опять повторение пунктов 1-3, которые приведут к правильному решению. Удачи!

svnnvs Был на днях Likes2 Messages10 5   На сайте: два года
Запись #193952. Добавлен: 2017-10-11 12:14:40
"Сложные судоку, как правило, не обходятся без пункта 4 «Альтернативы»" - как-то это не красиво!
Нравится + 0     4
nekonyash Online P E 19 Solver Rank   На сайте: 5 лет Добавлен: 2017-10-11 13:13:01 + 3
Про подбор/альтернативы/метод от противного (каждый понимает эти слова по-своему, так как нет единой терминологии) писалось в этом посте: https://grandgames.net/post/187044
Там очень много буков, но суть можно свести к тому, что не всегда альтернативы - это плохо. Просто стандартные методы анализа судоку - это не единственные методы, но незнание этих методов приводит к необходимости рассмотрения альтернатив. Главное, что у судоку есть одно единственное решение.
svnnvs Был на днях 5   На сайте: два года Добавлен: 2017-10-11 14:37:11 + 1
А где почитать про эти нестандартные методы? Подскажите пожалуйста.
nekonyash Online P E 19 Solver Rank   На сайте: 5 лет Добавлен: 2017-10-11 14:50:57 + 0
Вот, что я читала (англ): http://www.sudokuwiki.org/Introducing_Chains_and_Links
svnnvs Был на днях 5   На сайте: два года Добавлен: 2017-10-11 15:00:37 + 0
Спасибо большое. rose

Нужна ли Вам функция покупки игровых монет за настоящие деньги?
Да
Нет

Игроки месяца
WifeWolf yarus
Habi230964 abramka59
7298122 vk336665627
Irbiska 22yjz
rucha EVA-dragon
Bruno tonybola
serggio1974 mumof
tis Olesenka
SOLGAS NATAKAPA
0302elisej 11589811111
Новое на сайте
Пятнашки №33421
Какуро №33433
Хитори №33418
Японская мозаика №32798
№32724
№33480
№32846
№33085
№33425
Японский кроссворд №25035
Пазл №23996
Филиппинский №3587
Судоку №20109
Флеш игра №2151
Денди онлайн №168
Шахматная задача №9699
Ключворды №3162
Филворд №4236
Загадка №360
ADB finder
Релама Ads Google Yandex