Эвристический решатель судоку

[asm0dey]

Очевидно, что если после последовательного прохода всех 4 вариантов на каждой ячейке ни одна не заполнилась — надо
1) Сохранить состояние поля
2) Заполнить первую ячейку первым теоретически подходящим числом
3) Запомнить что и чем запомнили
4) Гонять МЕТА до полного заполнения/противоречия

при противоречии вернуться к последнему сохраненному состоянию и изменить шаг 2).

[Juggler]

Очень хотелось уйти от неэффективного перебора, а вариант «фиксируем значение в какой-то ячейке и гоняем алгоритм» очень близок к полному перебору. Точнее — к полному перебору прогнозов.

[asm0dey]

Бывают судки, которые нельзя решить на чистой логике, без предположений.

[Juggler]

Можно на такой взглянуть? Может, еще пара алгоритмов в голову придет…

[asm0dey]

Ну взглянуть-то можно, но я сходу не найду )).

Тут надо зайти на какой-нить сайт с судками и пробовать, пробовать.

Мне попадались судки с десятками и сотнями решений.

[Juggler]

Это я делал. Тогда пришлось добавить 4-й для частичного перебора негативных вариантов.

Не было цели найти все решения — хотя бы одно, для большинства этого достаточно.

[Bodigrim]

Попробуйте вот такое, например:
005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700

[Juggler]

Не решает… Находит еще только две цифры. Буду думать.

[kliss]

Мой решил, секунды за четыре :-)

|1| |4| |5| |3| |2| |7| |6| |9| |8|
|8| |3| |9| |6| |5| |4| |1| |2| |7|
|6| |7| |2| |9| |1| |8| |5| |4| |3|
|4| |9| |6| |1| |8| |5| |3| |7| |2|
|2| |1| |8| |4| |7| |3| |9| |5| |6|
|7| |5| |3| |2| |9| |6| |4| |8| |1|
|3| |6| |7| |5| |4| |2| |8| |1| |9|
|9| |8| |4| |7| |6| |1| |2| |3| |5|
|5| |2| |1| |8| |3| |9| |7| |6| |4|

[guyfawkes]

а «ваш» — это какой, если не секрет?

[Juggler]

Я эти алгоритмы писал в виде программы на Delphi лет шесть назад. Вот, решил вернуться к вопросу — просто интересно.

[guyfawkes]

Не вполне понял ваш ответ :) Я обращался к kliss, который сказал, что некий «его» алгоритм решил все за 4 секунды.

[kliss]

Ну я его здесь не рекламировал. Написал на днях скриптик на руби, когда мне надоело в уме варианты просчитывать :-)

[guyfawkes]

Ну так поделитесь что ли алгоритмом.

[kliss]

Ну там почти то же самое что описывали в этих двух статьях, плюс, возможно, что-то еще.

github.com/stulentsev/sudoku-solver

[Bodigrim]

Мой — за 2 миллисекунды :)

[kliss]

Давай теперь письками меряться, у кого меньше :-)

[NickLion]

Ваш 4-й алгоритм при правильной реализации — это и есть перебор — поиск с возратом. А остальные алгоритмы просто урезают пространство поиска. Ну, во всяком случае на это так можно посмотреть. Т.е. в общем-то если всё сделано правильно, то алгоритм будет универсальным, просто в худшем случае вырождаться почти до полного перебора. Но смущает фраза в другом Вашем коментарии — «частичный перебор» — что имеется в виду?

[Juggler]

Частичный перебор — перебираем только прогнозные варианты. 4-й включается в последнюю очередь и только для поиска негативного результата «этой цифры здесь быть не может». Обычно неплохо работает, когда поле уже немного заполнено.

[NickLion]

А, т.е. если на первой получили, что всё гуд, то такое решение не принимается?

[NickLion]

«всё гуд» — это конечно, «всё хорошо» :-D

[Juggler]

Да, учитываю только негативный результат — чтобы уменьшить прогнозы. Обычно ячейки с минимальной длиной прогноза — это два варианта в ячейке. Если отбросить один, второй заполняет ячейку.

[NickLion]

Ясно, значит я просто неверно понял описание. Подумал, что под

Если результат положительный, но поле заполнено не полностью, берем следующую прогнозную цифру или следующее поле.

скрывается рекурсия/итерация со стеком.

[Juggler]

Это вопрос конкретной реализации. У себя — старался экономить память и все делал на циклах.

[Yakhnev]

Не могу сказать, какая скорость работы у Вашего алгоритма, но алгоритм на основе танцующих ссылок Кнута решает несколько тысяч судоку любой сложности за секунду. Попробуйте провести сравнение.

[ilyanik]

Этот алгоритм может быть и эффективен, но всё равно в его основе лежит перебор. И O(N^5) памяти.

[ilyanik]

Вот здесь описано более 30! эвристик. И они тоже решают не всё :)

[st0ne_c0ld]

Кстати там, в целом, используется очень правильный метод. Сначала подбор простыми алгоритмами и если ни один из них не подошел — используются более сложные (и т.д.) пока не будет найден приемлемый вариант хода. Все варианты не пробовал, несколько раз добегало до середины, но в итоге решение нашлось.

[zim32]

Я один прочитал эротический? )