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

Инструкция по решению судоку от 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: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

Ваше отношение к турнирам на сайте
А что еще за турниры?
Иногда участвую
Не участвую по другим причинам (напишите в комментариях)
Не участвую, так как время проведения мне не подходит.
Не участвую, так как не люблю решать на скорость, мне нравится решать не спеша.
Не участвую, так как точно знаю, что проиграю.

Игроки месяца
yarus mikl
dikey753 mumof
PALKEN abramka59
Irbiska Habi230964
rof23 Bruno
vk336665627 246689jhgf
mvp64 lencha
7298122 odidi
NATAKAPA marisha067
arev Betelgeize
Новое на сайте
Пятнашки №38459
Какуро №38500
Хитори №38487
Японская мозаика №37985
№37588
№38407
№38392
№38297
№37619
№38518
Японский кроссворд №25806
Пазл №24884
Филиппинский №3687
Судоку №20397
Флеш игра №2151
Денди онлайн №168
Шахматная задача №9699
Ключворды №3470
Филворд №4889
Загадка №361
ADB finder
Реклама Ads Google Yandex