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 Messages17 5 Solver Rank
#193952 2017-10-11 12:14
"Сложные судоку, как правило, не обходятся без пункта 4 «Альтернативы»" - как-то это не красиво!
Нравится + 0     4   Поделиться
nekonyash Был несколько месяцев назад (2018-12-09 23:00:06) P E 19 Solver Rank 2017-10-11 13:13 + 3
Про подбор/альтернативы/метод от противного (каждый понимает эти слова по-своему, так как нет единой терминологии) писалось в этом посте: https://grandgames.net/post/187044
Там очень много буков, но суть можно свести к тому, что не всегда альтернативы - это плохо. Просто стандартные методы анализа судоку - это не единственные методы, но незнание этих методов приводит к необходимости рассмотрения альтернатив. Главное, что у судоку есть одно единственное решение.
svnnvs Был час назад 5 Solver Rank 2017-10-11 14:37 + 1
А где почитать про эти нестандартные методы? Подскажите пожалуйста.
nekonyash Был несколько месяцев назад (2018-12-09 23:00:06) P E 19 Solver Rank 2017-10-11 14:50 + 0
Вот, что я читала (англ): http://www.sudokuwiki.org/Introducing_Chains_and_Links
svnnvs Был час назад 5 Solver Rank 2017-10-11 15:00 + 0
Спасибо большое. rose
Ваше отношение к турнирам на сайте
А что еще за турниры?
Иногда участвую
Не участвую по другим причинам (напишите в комментариях)
Не участвую, так как время проведения мне не подходит.
Не участвую, так как не люблю решать на скорость, мне нравится решать не спеша.
Не участвую, так как точно знаю, что проиграю.
Sinicin62 gogo2908
40a gst4198905
gst1444693 mumof
dikey753 Irbiska
belyak62 rof23
araccheewa2010 istra
Alta_Bulochkina pelican
gst9194925 nas54
Spichenka tis
gst8016382 Bruno
Новое на сайте
Пятнашки №65557
Какуро №65544
Хитори №65527
Японская мозаика №65467
№65505
№63486
№65536
№65534
№65554
№63738
№54467
Ключворды №65482
Филиппинский №64986
№65538
№65558
№65555
Японский кроссворд №28846
Пазл №29752
Судоку №21351
Флеш игра №2153
Денди онлайн №5686
Шахматная задача №9699
Филворд №7286
Загадка №367
ADB finder
Реклама Ads Google Yandex
:)