Menu GrandGames.net
Русский
⍆ ⛹ ⎕ ⌕

Инструкция по решению судоку от 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 Messages20 6
#193952 2017-10-11 12:14
"Сложные судоку, как правило, не обходятся без пункта 4 «Альтернативы»" - как-то это не красиво!
Нравится + 0     4   Поделиться
nekonyash Был несколько дней назад 19 2017-10-11 13:13 + 3
Про подбор/альтернативы/метод от противного (каждый понимает эти слова по-своему, так как нет единой терминологии) писалось в этом посте: https://grandgames.net/post/187044
Там очень много буков, но суть можно свести к тому, что не всегда альтернативы - это плохо. Просто стандартные методы анализа судоку - это не единственные методы, но незнание этих методов приводит к необходимости рассмотрения альтернатив. Главное, что у судоку есть одно единственное решение.
svnnvs Был на днях 6 2017-10-11 14:37 + 1
А где почитать про эти нестандартные методы? Подскажите пожалуйста.
nekonyash Был несколько дней назад 19 2017-10-11 14:50 + 0
Вот, что я читала (англ): http://www.sudokuwiki.org/Introducing_Chains_and_Links
svnnvs Был на днях 6 2017-10-11 15:00 + 0
Спасибо большое. rose
Нравится ли Вам новая игра "Память"
Да
Еще не пробовал
Нет
NATAKAPA NoBody
radost Bruno
LLL25 mikl
Irbiska Morsmordre
mamo4ka lulasha0809
gst3150111 mukha
igor1960q 22yjz
rof23 watson4019
babirussa 2233002485101
Yoch.25 belyak62
Новое на сайте
Пятнашки №78893
Какуро №82134
Хитори №82042
Японская мозаика №79725
№82113
№81535
№82106
№81905
№82090
№82132
№54467
Ключворды №82000
Филиппинский №80778
№82101
№82127
№82133
№82120
№82131
Японский кроссворд №30882
Пазл №33037
Судоку №22018
Флеш игра №2153
Денди онлайн №5686
Шахматная задача №9699
Филворд №8863
Загадка №372
ADB finder
Реклама Ads Google Yandex
:)
Вернуть свернутое окно