Menu GrandGames.netRU

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

Данный алгоритм по решению судоку 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 Messages14 5
#193952 2017-10-11 12:14
"Сложные судоку, как правило, не обходятся без пункта 4 «Альтернативы»" - как-то это не красиво!
Нравится + 0     4
nekonyash Был два часа назад P E 19 Solver Rank 2017-10-11 13:13 + 3
Про подбор/альтернативы/метод от противного (каждый понимает эти слова по-своему, так как нет единой терминологии) писалось в этом посте: https://grandgames.net/post/187044
Там очень много буков, но суть можно свести к тому, что не всегда альтернативы - это плохо. Просто стандартные методы анализа судоку - это не единственные методы, но незнание этих методов приводит к необходимости рассмотрения альтернатив. Главное, что у судоку есть одно единственное решение.
svnnvs Сегодня был на сайте 5 2017-10-11 14:37 + 1
А где почитать про эти нестандартные методы? Подскажите пожалуйста.
nekonyash Был два часа назад P E 19 Solver Rank 2017-10-11 14:50 + 0
Вот, что я читала (англ): http://www.sudokuwiki.org/Introducing_Chains_and_Links
svnnvs Сегодня был на сайте 5 2017-10-11 15:00 + 0
Спасибо большое. rose
Ваше отношение к турнирам на сайте
А что еще за турниры?
Иногда участвую
Не участвую по другим причинам (напишите в комментариях)
Не участвую, так как время проведения мне не подходит.
Не участвую, так как не люблю решать на скорость, мне нравится решать не спеша.
Не участвую, так как точно знаю, что проиграю.
k336665627 mumof
dikey753 istra
babyshka62 staska
Irbiska rof23
Habi230964 abramka59
GimliG NINA0402
LauraMenshikova PALKEN
feliciya carlson
Elvira121 petrovna
larin18 vk286575639
Новое на сайте
Пятнашки №44739
Какуро №44733
Хитори №44693
Японская мозаика №44578
№44677
№44708
№44463
№44705
№43630
№44742
Японский кроссворд №27080
Пазл №26743
Филиппинский №3800
Судоку №20781
Флеш игра №2151
Денди онлайн №168
Шахматная задача №9699
Ключворды №3846
Филворд №5750
Загадка №361
ADB finder
Реклама Ads Google Yandex
:)

Согласно регламенту GDPR, информируем Вас, что наш сайт использует файлы Coockies Вашего браузера. Они необходимы для корректного выполнения многих функций сайта, например авторизации, сохранения настроек и головоломок.

Кроме того, информация о вашем поведении, собранная при помощи Coockies может использоваться компаниями Google и Yandex, чьи аналитические и рекламные модули размещены на данном сайте. Если вы не желаете предоставлять указанную информацию, пожалуйста отключите Coockies в настройках браузера, либо откажитесь от использования данного сайта!