Comments 11
Емнип уникальность цифр в диагоналях входит в правила судоку
Полный перебор цифр‑кандидатов в свободных клетках таблицы судоку компьютер не потянет.
Чойта вдруг? Я вот сейчас глянул - решалка судоку, написанная мной аж в 2010 году, прекрасно решает судоку тупым перебором "в лоб". Естественно, если на поле только одна подсказка, то перебирать она будет долго, но при этом счетчик найденных решений будет постоянно расти. Чтобы найти 101 решение из вашего примера, ей на современном железе понадобилась - ну, может, секунда, не замерял. На стареньком железе умножаем время на десять, но в общем и целом тоже было вполне терпимо.
Соглашусь с комментом выше. Метод ветвей и границ даёт решение практически мгновенно. И решение выглядит более эстетично и короче (java): 22 строки вместе с выводом.
Жаль, что такая хорошая глубокая статья омрачена неосторожным ложным тезисом вначале, который ломает структуру.
Я когда-то писал скрипт, который решает судоку только за счёт эвристик, без перебора.
Для пробы я использовал судоку из мобильной игры (ввод и вывод - вручную). По итогу прохождения двух или трёх сотен примеров, я обнаружил, что когда эвристики не хватает, нужно перебрать альтернативные значения одной ячейки (подставлял значение в ручную и запускал продолжение эвристического решения).
Как вариант, ещё можно использовать SMT solver, например z3. Запись в таком формате получится самой лаконичной.
Да, было как-то давно, решил судоку, а с ответом не сходится. Проверил у себя — всё правильно. Оказывается, бывают "варианты". Хоть и написано было в инструкции, что правильный ответ может быть только единственным — на заборе тоже много чего написано.
Всем спасибо за критику!
Возможно я, «не посвящённый в тайны жанра» − это цитата из статьи, не прав, считая что
«… компьютер не потянет». Было бы интересно узнать и сравнить время получения разными методами всех 26918 вариантов ответа (с выводом в файл для дальнейшего анализа) на судоку №149 из статьи. Если брать по секунде на вариант, то получаем 26918/3600 =7,47 часа.
Если брать по секунде на вариант
С чего бы так долго? У меня даже на старом Pentium 4 за секунду несколько десятков вариантов находило.
Сейчас запустил, проверил. Полный обсчет судоку №149 занял примерно 16 секунд на моем Ryzen 3700x, число вариантов ответа сходится - 26918. Лезть в старый код неохота, поэтому более точно время не скажу и дамп всех найденных вариантов в файл тоже привинчивать не буду.
И это однопоточный код. Если прикрутить многопоточность, то скорость обсчета вырастет в разы.
Код при этом тупой как пробка: обычный рекурсивный перебор с возвратом.
Спасибо за тестирование.
Секунду назначили berez в своём первом комментарии.
Учёт системы ограничений отсекает до 27 ячеек, при этом даже тупой перебор для остальных ячеек даёт решение за приемлемое время, и можно анализировать полученные ответы. А простой перебор, конечно, не является оптимальным алгоритмом.
Так я и есть berez. И то, о чем я говорил - это что решалка за секунду нашла 101 решение. С чего вдруг взялась секунда на решение - непонятно.
Впрочем, не суть. Чтоб разговор стал предметным - выложил старый код в гитхаб, вдруг интересно. Решалка интерактивная, тычем в поле - появляется цифра, тычем еще раз - цифра меняется на следующую возможную. При любом тычке перезапускается тред с обсчетом вариантов. Первый найденный выводится на экран, остальные просто подсчитываются. Стирать цифры - только перезапуском всей программы. :)
Помнится, когда я с этим всем игрался, время полного обсчета довольно сильно менялось. Иногда единственный вариант решения вылезал быстро, иногда - после ощутимой задержки. Зависит это, естественно, от порядка обсчета. Возможно, решалку можно оптимизировать так, что она будет работать за доли секунды, но мне это было как-то не нужно.
Как «подправить» неправильные судоку. Алгоритм решения судоку, использующий систему ограничений