Comments 30
Очевидно, что если после последовательного прохода всех 4 вариантов на каждой ячейке ни одна не заполнилась — надо
1) Сохранить состояние поля
2) Заполнить первую ячейку первым теоретически подходящим числом
3) Запомнить что и чем запомнили
4) Гонять МЕТА до полного заполнения/противоречия
при противоречии вернуться к последнему сохраненному состоянию и изменить шаг 2).
1) Сохранить состояние поля
2) Заполнить первую ячейку первым теоретически подходящим числом
3) Запомнить что и чем запомнили
4) Гонять МЕТА до полного заполнения/противоречия
при противоречии вернуться к последнему сохраненному состоянию и изменить шаг 2).
Очень хотелось уйти от неэффективного перебора, а вариант «фиксируем значение в какой-то ячейке и гоняем алгоритм» очень близок к полному перебору. Точнее — к полному перебору прогнозов.
Бывают судки, которые нельзя решить на чистой логике, без предположений.
Можно на такой взглянуть? Может, еще пара алгоритмов в голову придет…
Ну взглянуть-то можно, но я сходу не найду )).
Тут надо зайти на какой-нить сайт с судками и пробовать, пробовать.
Мне попадались судки с десятками и сотнями решений.
Тут надо зайти на какой-нить сайт с судками и пробовать, пробовать.
Мне попадались судки с десятками и сотнями решений.
Попробуйте вот такое, например:
005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700
005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700
Не решает… Находит еще только две цифры. Буду думать.
Мой решил, секунды за четыре :-)
|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|
|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|
а «ваш» — это какой, если не секрет?
Я эти алгоритмы писал в виде программы на Delphi лет шесть назад. Вот, решил вернуться к вопросу — просто интересно.
Ну я его здесь не рекламировал. Написал на днях скриптик на руби, когда мне надоело в уме варианты просчитывать :-)
Ну так поделитесь что ли алгоритмом.
Ну там почти то же самое что описывали в этих двух статьях, плюс, возможно, что-то еще.
github.com/stulentsev/sudoku-solver
github.com/stulentsev/sudoku-solver
Мой — за 2 миллисекунды :)
Ваш 4-й алгоритм при правильной реализации — это и есть перебор — поиск с возратом. А остальные алгоритмы просто урезают пространство поиска. Ну, во всяком случае на это так можно посмотреть. Т.е. в общем-то если всё сделано правильно, то алгоритм будет универсальным, просто в худшем случае вырождаться почти до полного перебора. Но смущает фраза в другом Вашем коментарии — «частичный перебор» — что имеется в виду?
Частичный перебор — перебираем только прогнозные варианты. 4-й включается в последнюю очередь и только для поиска негативного результата «этой цифры здесь быть не может». Обычно неплохо работает, когда поле уже немного заполнено.
А, т.е. если на первой получили, что всё гуд, то такое решение не принимается?
«всё гуд» — это конечно, «всё хорошо» :-D
Да, учитываю только негативный результат — чтобы уменьшить прогнозы. Обычно ячейки с минимальной длиной прогноза — это два варианта в ячейке. Если отбросить один, второй заполняет ячейку.
Не могу сказать, какая скорость работы у Вашего алгоритма, но алгоритм на основе танцующих ссылок Кнута решает несколько тысяч судоку любой сложности за секунду. Попробуйте провести сравнение.
Вот здесь описано более 30! эвристик. И они тоже решают не всё :)
Кстати там, в целом, используется очень правильный метод. Сначала подбор простыми алгоритмами и если ни один из них не подошел — используются более сложные (и т.д.) пока не будет найден приемлемый вариант хода. Все варианты не пробовал, несколько раз добегало до середины, но в итоге решение нашлось.
Я один прочитал эротический? )
UFO just landed and posted this here
Sign up to leave a comment.
Эвристический решатель судоку