Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 35
Rust-солвер почти всегда опережает на 1-3 порядка питоновский солверВы здесь используете математический смысл «порядка»? Т.к. на картинке я не увидел разницу даже на один порядок.
Не понял, за какое время ваша программа решила тест 22336? У вас там шкала закончилась.
За час не решилась, остановлено по таймауту — это то, что обозначено '+' в оригинальной таблице-сравнении. Для графиков я просто подставил значение 10000 секунд, чтобы не с бесконечностью оперировать.
Значит, не все тесты решаются.
Да, из всего сайта webpbn.com 6 черно-белых не решаются до конца и еще больше цветных.
Тогда утверждение "солвер умеет решать все пазлы с сайтов https://webpbn.com" не соответствует действительности.
«решать» != «находить решения». Речь здесь о принципиальной возможности, а не о конечном результате. Например большинство солверов не умеют решать цветные кроссворды. Хотя формально вы правы — я не добавил поддержку blotted-кроссвордов, хотя в Python-солвере она была.
Хм… При всем уважении, решать — это именно находить решения. Что толку от солвера, если он потратит год на решение и ничего не найдет ?
У меня написано «умеет решать», а вы трактуете как «может решить». Вы ведь не станете говорить, что шахматист, который проигрывает партию другому «не умеет играть», он скорее «не смог победить». А вот те солверы, которые не умеют решать цветные — они как шахматисты, которые в принципе не умеют играть в го. Иначе говоря, несмотря на то что, глаголы «решать» и «решить» похожи — это все таки разные глаголы. Первый — о процессе, второй — о результате.
Запустил #22336 на машине послабее — через 26 часов нашлось два решения (94020 сек). Все же получилось значительно меньше года. Конечно ваш солвер решает ту же задачу меньше чем за 2 минуты и это очень круто.
Вызов принят
Не пробовали написать алгоритм составления/решения филиппинских кроссвордов?
Никогда не слышал о них до этого, но на первый взгляд кажется, что с ними попроще должно быть.
Ну вот один из примеров.
Я пробовал лет 10 назад. Правда, еще не знал, что они называются филиппинскими. Решение гораздо проще, а вот составление делать не пробовал. Исходников, к сожалению, не сохранилось.
Ага.
Реквестирую прогон на www.spoj.com/problems/JCROSS
Там как раз на Rust никто не решал ещё.
Там как раз на Rust никто не решал ещё.
Это дело конечно хорошее, только там Rust 1.14.0 используется, где куча сахара еще не введена и, например, у итераторов значительно меньше методов. Но для спортивного интереса думаю можно попробовать переделать под Rust образца 2016.
Попробовал загнать туда минимальный пример — получил таймаут. Возможно там билдится без оптимизаций, поэтому получается медленный debug-код.
Там есть проблемный кроссворд. Попробуй не делать backtracking у 198-ого по порядку кроссворда. У меня с ним были проблемы.
поменял стратегию выбора кандидата для бэктрэкинга и все тесты удалось решить
Ну вот, работает машинка-то. Нам бы только иностранное ругать © :)
Быстро у вас получилось. За 12 подходов всего.
Быстро у вас получилось. За 12 подходов всего.
Половину этих подходов я пытался выяснить, почему выдает 'Wrong Answer' и при этом не дает никаких подсказок, что же пошло не так. Оказалось, что никакие другие символы, кроме '.' и '#' нельзя писать, иначе задача сразу считается проваленной. А у меня для неопределенных (нерешенных) клеток раньше выводил символ '?'.
Вторая половина запусков — это да, здесь я пытался поменять стратегию бэктрэкинга так, чтобы без таймаута все решить.
Вторая половина запусков — это да, здесь я пытался поменять стратегию бэктрэкинга так, чтобы без таймаута все решить.
Признаюсь, я читал на скроллинге, но описание используемых шагов для решения прочёл внимательно. Я правильно понял, что для решения цветных кроссвордов используется такой же набор алгоритмов, что и для чёрно-белых? То есть, для одноцветных (отсутствие цвета и точки не цвет).
Ведь решение цветных кроссвордов сводится к решению одноцветных — берётся каждый цвет отдельно и решается как одноцветный. Зашли в тупик — переключились на другой цвет, но с учётом решения по предыдущему цвету.
Или именно такой алгоритм для многоцветных кроссвордов и был реализован, а я просто не увидел?
Ведь решение цветных кроссвордов сводится к решению одноцветных — берётся каждый цвет отдельно и решается как одноцветный. Зашли в тупик — переключились на другой цвет, но с учётом решения по предыдущему цвету.
Или именно такой алгоритм для многоцветных кроссвордов и был реализован, а я просто не увидел?
Все этапы решения — параметрические по типу блока (BinaryBlock или ColoredBlock). То есть все функции имеют примерно такую сигнатуру
fn solve<B: Block>(...);. Алгоритмы ничего не знают, о том что они решают, потенциально можно добавить еще какую-нибудь пару типов impl Block for SomeOtherBlock; impl Color for SomeOtherColor помимо имеющихся сейчас BinaryColor + BinaryBlock; MultiColor + ColoredBlock, которые будут задавать еще какую-то схему взаимодействия между отдельными числовыми блоками и клетками нонограмм и все алгоритмы должны без проблем эту схему подхватить. Короче говоря, черно-белые — это не частный случай цветных, а совершенно отдельная схема.О, мой solver в статистике (Syromolotov). С тех пор добавил несколько идей по backtracking-у
И вот тут начинается самое интересное. Распишу по этапам эволюции моего backtracking
1) Очевидно (может и не очевидно, но эксперементально проверено), что выбор клеток по порядку не лучший вариант.
2) Логично предположить, что если выбрать клетку, которая на этапе «probing» даёт больше закрашиваемых клеток, то это даст лучший результат. Тут у меня появилось два метода (я писал только черно-белый решатель):
а) Искать клетку у которой один цвет даёт максимальный результат и начинать с него.
б) Искать клетку, у которой минимум по двум цветам (черный и белый) даёт максимальный результат и начинать с максимального цвета.
Метод б) эксперементально даёт лучший результат. Но голый этап 2 тоже не продуктивный, так как на каждом этапе поиска клетки (уровне рекурсии backtracking-а) приходится делать probing по всем незакрашенным клеткам.
3) А что если на каждом уровне рекурсии backtracking-а делать probing не по всем незакрашенным клеткам, а только по тем, у которой набор закрашиваемых клеток пересекается с набором закрашиваемых клеток с выбранной клеткой на предыдущем этапе. Для этого после каждого probinga клетки его закрашиваемые клетки записываются в список закрашиваемых. И наоборот в закрашенную после probingа клетку помещается список тех клеток, которые её закрасили. Данный этап дал огромный скачек в решений, который задвинул меня в список лидирующих солверов в webpbn.com/survey
4) Последний этап на данный момент (который уже писался после попадания в webpbn.com/survey). Проблемы есть из-за последовательного выполнения рекурсии. Покажем на примере. Допустим у нас есть 3 уровня рекурсии
1 уровень. Мы нашли клетку1 и пошли в черный цвет
2 уровень. Мы нашли клетку2 и пошли в чёрный цвет
3 уровень. Мы нашли клетку3 и пошли в черный цвет. Узнали, что черный цвет ошибочен проверили белый цвет. Узнали что он тоже ошибочен. И пошли на уровень ниже. То есть на уровень2. И там меняем клетку2 на белую и возвращаемся в уровень3.
А что если закрашенные клетки на уровне 3 и закрашенные клетки на уровне 2 не зависимы друг от друга (например находятся вообще в разных углах кроссворда и никак друг на друга не влияют). Тогда получается, что мы зря вернулись на уровень2. А сразу могли бы вернутся на уровень 1 и проверять белый цвет Клетки1. Если между зависимыми уровнями, например 10 независимых, то это огромная работа сделанная впустую.
Для того, чтобы выявить зависимость между уровнями, я при закрашивании клеток в probing-е, помечаю какие клетки повлияли на выбор этого цвета и смотрю, в каком уровне они были закрашены. После этого можно смело пропускать уровни, которые не повлияли на закрашивания уровня n.
4-й этап дал так же очень хороший скачок в решении.
Здесь начинает играть большую роль, какая из клеток будет выбрана в качестве следующего расширения потенциального решения.
И вот тут начинается самое интересное. Распишу по этапам эволюции моего backtracking
1) Очевидно (может и не очевидно, но эксперементально проверено), что выбор клеток по порядку не лучший вариант.
2) Логично предположить, что если выбрать клетку, которая на этапе «probing» даёт больше закрашиваемых клеток, то это даст лучший результат. Тут у меня появилось два метода (я писал только черно-белый решатель):
а) Искать клетку у которой один цвет даёт максимальный результат и начинать с него.
б) Искать клетку, у которой минимум по двум цветам (черный и белый) даёт максимальный результат и начинать с максимального цвета.
Метод б) эксперементально даёт лучший результат. Но голый этап 2 тоже не продуктивный, так как на каждом этапе поиска клетки (уровне рекурсии backtracking-а) приходится делать probing по всем незакрашенным клеткам.
3) А что если на каждом уровне рекурсии backtracking-а делать probing не по всем незакрашенным клеткам, а только по тем, у которой набор закрашиваемых клеток пересекается с набором закрашиваемых клеток с выбранной клеткой на предыдущем этапе. Для этого после каждого probinga клетки его закрашиваемые клетки записываются в список закрашиваемых. И наоборот в закрашенную после probingа клетку помещается список тех клеток, которые её закрасили. Данный этап дал огромный скачек в решений, который задвинул меня в список лидирующих солверов в webpbn.com/survey
4) Последний этап на данный момент (который уже писался после попадания в webpbn.com/survey). Проблемы есть из-за последовательного выполнения рекурсии. Покажем на примере. Допустим у нас есть 3 уровня рекурсии
1 уровень. Мы нашли клетку1 и пошли в черный цвет
2 уровень. Мы нашли клетку2 и пошли в чёрный цвет
3 уровень. Мы нашли клетку3 и пошли в черный цвет. Узнали, что черный цвет ошибочен проверили белый цвет. Узнали что он тоже ошибочен. И пошли на уровень ниже. То есть на уровень2. И там меняем клетку2 на белую и возвращаемся в уровень3.
А что если закрашенные клетки на уровне 3 и закрашенные клетки на уровне 2 не зависимы друг от друга (например находятся вообще в разных углах кроссворда и никак друг на друга не влияют). Тогда получается, что мы зря вернулись на уровень2. А сразу могли бы вернутся на уровень 1 и проверять белый цвет Клетки1. Если между зависимыми уровнями, например 10 независимых, то это огромная работа сделанная впустую.
Для того, чтобы выявить зависимость между уровнями, я при закрашивании клеток в probing-е, помечаю какие клетки повлияли на выбор этого цвета и смотрю, в каком уровне они были закрашены. После этого можно смело пропускать уровни, которые не повлияли на закрашивания уровня n.
4-й этап дал так же очень хороший скачок в решении.
Круто, что нашелся автор одного из самых быстрых солверов!
По пунктам 1 и 2: я для стратегии выбора лучшего кандидата изучал это исследование и на моем солвере лучший результат показала стратегия Sqrt (см. раздел V. EXPERIMENTS).
Пункт 3 — это что-то новенькое, надо будет у себя попробовать сделать.
Пункт 4 очень похож на стратегию «срезания» ветвей дерева поиска, называемую «backjumping». У меня были планы по ее реализации, но руки пока не дошли.
Спасибо за подробное описание идей.
По пунктам 1 и 2: я для стратегии выбора лучшего кандидата изучал это исследование и на моем солвере лучший результат показала стратегия Sqrt (см. раздел V. EXPERIMENTS).
Пункт 3 — это что-то новенькое, надо будет у себя попробовать сделать.
Пункт 4 очень похож на стратегию «срезания» ветвей дерева поиска, называемую «backjumping». У меня были планы по ее реализации, но руки пока не дошли.
Спасибо за подробное описание идей.
Круто, что нашелся автор одного из самых быстрых солверов!
К сожалению, Данная статистика теряет актуальность.Страница webpbn.com/survey не обновлялась с
Last Update: Wed Sep 25 06:35:01 PDT 2013
А товарищ Jan Wolter (jan) (создатель этого сайта, собиратель этой статистики, автор pbnsolver) — умер в декабре 13-го — январе 14-го
Сейчас дорабатывал п.4.
Раньше на n-ом уровне делался probing и по всем закрашенным клеткам этого уровня выстраивался общий список уровней, от которых они зависят.
Сейчас этот список индивидуальный для каждой закрашенной клетки.
К п.4 дорабатывается пункт 5.
Сейчас работает так
Если в уровень 20 находилась ошибка, которая зависела от 10-го уровня, то сразу стираются все уровни после 10. Десятый уровень исправлялся и дальше снова шёл 11 уровень.
Пытаюсь доработать, чтобы исправлялся уровень 10. Уровни с 11 по 19 не трогаются (если они не зависят от 10-го). И снова запускается 20 уровень.
Раньше на n-ом уровне делался probing и по всем закрашенным клеткам этого уровня выстраивался общий список уровней, от которых они зависят.
Сейчас этот список индивидуальный для каждой закрашенной клетки.
К п.4 дорабатывается пункт 5.
Сейчас работает так
Если в уровень 20 находилась ошибка, которая зависела от 10-го уровня, то сразу стираются все уровни после 10. Десятый уровень исправлялся и дальше снова шёл 11 уровень.
Пытаюсь доработать, чтобы исправлялся уровень 10. Уровни с 11 по 19 не трогаются (если они не зависят от 10-го). И снова запускается 20 уровень.
Было бы занятно, если бы нашелся алгоритм лучше, чем SAT солвер.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решение японских кроссвордов c P̶y̶t̶h̶o̶̶n̶ Rust и WebAssembly