Comments 20
Я делал перебором по строкам и затем по столбцам с одной оптимизацией: в одной строке/столбце можно стекать все группы влево, затем вправо и быстро таким способом обнаружить закрашенные клетки, они могут позднее помочь ускорить решение по перпендикулярному направлению
Круто. Кстати, самые тупые алгоритмы перебором очень хорошо распараллеливаются.
Оранжевым помечены «нерешаемые» клетки.Я бы поспорил с Википедией, потому что метод частичного перебора тоже можно считать одним из способов решения.
Например, для правой части 1 легко находится, поскольку куда её не поставь — везде ломается конфигурация следующей единицы после тройки. И это делается просто «в уме», беглым просмотром. Как это алгоритмизировать — без понятия, но я раздумывал над алгоритмом решения чёрно-белого кроссворда.
И вопрос к автору: есть быстрая реализация для чёрно-белого варианта? Цветной-то заведомо легче.
Если говорить только про алгоритмическую часть (не улучшаем ничего другого), то в черно-белом варианте, к сожалению, замена цикла на частичные суммы, как в разделе, где решение задач с олимпиад, не ухудшает и не меняет время (по крайней мере у меня чуть-чуть меньше максимальное время).
Можно рассмотреть такой вариант — каждой строке и столбцу привязать два дерева Фенвика с хорошей константой и памятью за линию (лучше чем у ДО), один для черных клеток, другой для белых, и тогда CanPlace работает за log(n), но и изменение массива в одном месте работает за log(n). По моим ощущениям это может побить сложные кроссворды но почти наверняка поднимет average time за счет побочных операций. А вообще можно в программу добавить счетчик, который будет считать реальное количество тактов в CanPlace — может оказаться, что реально на входных данных оно вызывается очень мало раз, и разные структуры только портят все.
Дерево Фенвика не подходит к цветным кроссвордам, но если бы подходило, положение наверняка было бы плохо, так как состояний у клетки больше, т.е. изменение клетки массива не значит, что мы нашли ответ для этой клетки, а просто обновили список доступных вариантов.
Все равно задача из википедии выглядит как странный пример, достаточно попробовать ставить оставшиеся ряды/столбцы вдоль стенок и легко заметить что в самом левом ряду столбец вверху стоять не может. Дальше все решается вашим предыдущим методом. Алгоритмически это может выглядеть как попытка найти невязку за определенное кол-во шагов. Перебирать нужно столбцы/строки с наименьшим кол-вом вариантов в нашем случае существует всего 3 возможных положения для левой четверки, при этом два из них пересекаются во всех клетках за исключением одной.
Второй вариант у клеток можно считать дискретные "вероятности" и начинать с наиболее вероятных в данном случае это будет три нижних клетки которые и станут решением.
Вот кстати частичные суммы (сделал для этого отдельную ветку) — https://github.com/Izaron/Nonograms/tree/blacks
Интересно, сколько всего тестов получится пройти.
В этих тестах может быть не единственное решение, или недетерминированный результат. Алгоритм из статьи решает 173/300 паззлов за 0.11 секунды, т.е. именно столько тестов решаются логикой.
Если форсированно ставить в "непонятную" клетку белый цвет и идти дальше, полностью решаются 203/300, это 0.36 секунды. Исходник.
Такой тип задач — дают NP-полную и решай себе с разными фокусами и фортелями. Ограничение по времени 19 секунд. Можно пойти дальше так — собрать те 97 нерешаемых тестов, запустить на них бэктрекинг/полный перебор, начиная с самого маленького. Попутно надо следить за временем с high_resolution_clock, чтобы не пробить тайм-лимит, иначе 0 баллов. Еще может помочь отсечение по времени для каждого теста, чтобы не застрять на мерзком тесте.
50 100
1 1 1 1 2 3 3 4 1 7 2 7 5 3 9 3 2 2 1 0
2 1 2 3 1 5 1 7 2 4 5 14 3 2 1 1 3 0
2 1 1 3 4 7 1 7 13 1 4 2 1 1 5 3 0
2 2 1 1 4 7 1 18 6 6 2 3 6 3 0
1 1 5 7 1 8 5 5 7 6 1 1 1 5 3 0
1 4 7 2 5 5 4 5 7 5 1 3 4 4 0
1 1 5 7 1 18 2 10 9 1 1 1 4 0
1 4 7 2 14 6 4 18 1 1 0
1 1 5 7 14 32 5 0
4 2 1 4 7 11 8 12 4 2 1 1 5 0
3 1 5 7 3 8 24 3 6 1 5 0
3 5 5 6 3 12 5 3 5 13 1 1 2 4 0
2 8 1 5 6 2 6 12 15 1 1 0
1 10 1 5 6 7 2 3 15 2 1 1 1 1 1 0
4 1 2 5 6 1 1 6 7 6 2 4 6 5 2 1 2 0
4 3 1 6 5 1 1 5 3 1 2 3 2 1 9 3 5 2 2 1 0
4 2 1 6 5 1 4 2 1 2 2 1 2 12 3 6 1 2 1 0
4 1 6 6 1 1 1 2 1 1 1 1 2 2 1 7 10 3 2 1 0
5 6 6 2 1 3 1 2 1 8 9 3 8 2 1 1 1 1 0
1 16 11 3 1 2 1 1 2 1 1 2 6 10 2 1 3 0
16 5 2 1 2 1 1 1 1 3 8 5 2 2 1 2 0
2 14 4 5 1 2 2 3 1 2 3 6 2 3 2 1 1 3 0
1 3 11 4 5 2 1 2 1 1 2 1 2 7 7 2 3 1 0
2 4 10 4 5 1 1 4 1 6 1 2 7 3 5 2 4 1 0
1 6 9 8 2 3 2 2 1 1 2 1 1 1 9 2 7 1 1 0
1 2 3 1 8 4 1 1 4 1 1 1 1 1 1 11 7 2 3 0
2 1 1 2 7 7 3 1 1 1 1 1 2 3 3 5 4 3 1 0
4 2 1 6 5 1 1 1 1 1 1 3 1 1 4 4 1 4 1 0
5 1 1 2 6 1 5 2 1 1 2 3 3 10 2 4 0
6 1 1 1 8 8 1 1 2 1 1 8 2 9 2 3 2 0
7 2 1 2 1 2 1 1 1 1 1 4 1 2 2 14 3 3 2 1 1 0
8 2 2 1 1 1 1 5 1 1 1 1 2 2 1 7 6 3 1 2 1 0
3 4 1 1 3 1 3 1 1 2 2 1 1 1 3 2 3 5 5 1 1 1 0
5 3 4 2 3 5 1 1 1 5 2 1 3 4 5 4 1 2 0
5 3 4 3 7 1 1 3 1 1 1 1 3 1 6 8 3 2 2 1 2 0
3 1 3 4 6 3 1 1 1 1 6 1 1 7 2 6 2 1 1 0
3 6 1 8 3 1 1 1 1 1 5 2 4 1 4 4 1 2 1 0
6 3 15 2 2 2 1 5 1 2 4 1 6 3 1 2 1 1 2 0
9 17 10 2 1 2 4 9 2 1 1 1 1 0
8 2 4 4 6 2 2 4 7 1 1 3 2 3 1 0
5 2 1 4 4 7 3 1 3 4 3 1 7 1 0
5 2 5 4 4 4 5 6 3 5 1 3 2 1 1 2 1 1 0
9 3 4 4 2 7 6 2 2 1 10 7 7 1 1 1 1 0
2 6 3 2 3 3 7 4 4 2 12 18 1 0
8 7 3 2 2 6 2 8 14 2 4 4 1 0
7 5 7 2 6 2 3 1 17 2 4 2 2 1 6 0
6 5 5 8 7 8 19 5 3 1 7 0
3 1 7 5 2 4 3 2 8 4 1 2 14 1 2 1 1 1 8 0
3 1 7 5 4 14 6 3 2 2 2 11 2 1 5 9 0
4 7 5 16 1 1 3 2 8 2 7 2 4 1 3 2 2 0
1 1 1 4 1 25 0
4 4 1 1 24 0
1 3 4 1 16 6 0
1 1 6 1 1 5 2 10 1 0
1 1 7 1 2 4 2 13 0
2 1 9 1 4 5 5 0
1 3 4 3 1 1 5 1 2 5 3 0
3 3 2 3 3 1 9 4 4 0
1 1 1 6 7 1 7 2 4 0
1 2 1 3 1 3 2 1 2 3 3 4 0
1 2 3 1 3 3 3 4 1 4 0
4 4 3 6 2 1 4 0
1 4 1 1 3 8 3 0
2 5 1 3 3 1 3 0
3 2 5 1 1 3 3 4 0
2 3 10 1 1 6 6 0
1 1 1 13 3 1 4 3 6 0
1 1 16 6 4 5 0
2 18 1 10 4 0
1 23 1 1 6 1 3 0
23 1 5 3 0
11 8 1 15 0
9 1 5 3 4 5 0
7 11 5 1 1 3 3 3 2 0
5 15 4 1 2 2 2 3 2 0
2 17 4 2 3 3 1 0
20 3 1 2 3 2 5 0
1 22 2 2 3 2 5 0
1 11 3 4 2 1 3 3 2 4 0
9 1 1 4 4 1 1 4 1 2 0
9 1 2 7 1 1 1 1 4 2 0
8 2 8 2 1 1 5 2 0
7 2 3 6 2 1 3 1 1 4 3 0
5 1 2 2 4 2 1 1 5 3 0
4 2 4 3 1 3 2 4 4 0
3 10 2 1 1 1 2 6 2 0
2 1 4 4 3 1 2 1 1 1 1 4 2 0
1 14 1 2 1 1 1 4 0
1 12 8 1 2 1 6 0
11 4 1 2 1 3 1 3 1 0
1 2 8 4 1 1 2 3 1 2 3 0
1 1 9 1 1 1 1 2 1 1 2 3 2 0
12 1 1 1 1 2 1 1 1 8 0
10 1 2 1 1 2 4 1 2 8 0
1 8 1 2 1 1 1 2 2 1 2 1 1 4 0
12 1 2 1 1 2 1 1 1 1 7 0
5 6 2 1 1 4 1 1 2 1 7 0
4 4 1 1 1 5 1 1 3 1 5 0
2 6 1 2 1 2 1 1 4 4 1 0
1 7 1 1 1 1 1 2 2 1 1 1 0
7 1 2 1 1 2 1 5 1 1 2 0
7 3 3 1 4 1 1 1 2 3 0
5 5 1 3 1 4 3 1 2 4 0
4 7 1 2 1 1 3 1 1 1 3 1 0
12 7 1 3 1 3 4 1 0
1 4 5 4 2 1 1 1 1 1 4 1 0
11 1 1 1 2 1 2 1 1 4 2 0
5 7 1 1 1 1 2 1 2 4 2 0
6 3 1 2 1 2 1 1 2 2 6 1 0
4 4 4 2 1 8 1 1 5 1 0
2 11 5 1 1 4 8 0
13 2 2 1 2 7 0
2 8 5 2 1 3 5 0
2 2 1 3 3 3 3 1 3 5 2 0
2 8 4 4 3 9 0
2 10 1 3 7 3 3 7 0
14 5 6 3 8 0
2 10 5 2 2 14 5 0
12 6 4 2 5 8 1 4 0
6 3 1 1 8 3 4 3 2 1 4 0
9 9 3 5 3 1 2 4 0
1 3 4 9 6 4 1 3 4 3 0
1 2 3 6 1 6 3 1 1 4 3 0
2 6 6 2 10 5 1 2 4 0
1 4 3 5 5 4 4 2 8 0
2 4 9 7 1 1 3 3 1 8 0
1 2 4 8 8 3 1 3 7 0
1 1 10 6 4 6 4 1 5 0
1 1 4 11 1 4 5 3 1 0
2 1 14 3 10 2 2 1 1 1 0
14 5 3 5 2 2 1 2 0
1 1 2 3 3 2 1 6 4 5 2 0
1 2 13 2 6 11 2 1 0
1 1 2 18 5 4 8 2 0
1 1 1 3 3 2 9 2 3 2 6 1 0
1 1 6 1 12 1 4 2 0
1 1 5 3 4 2 3 3 0
1 1 6 1 5 2 3 1 0
1 8 5 1 2 0
2 14 1 2 0
3 1 5 3 2 0
5 2 1 1 1 5 1 1 1 2 0
5 1 1 2 2 12 1 1 3 0
5 2 3 1 1 2 1 2 1 1 4 0
4 1 1 1 2 1 1 1 4 0
1 3 2 1 1 1 1 3 5 0
2 4 1 1 1 2 5 0
5 4 1 1 1 1 2 4 0
11 1 1 1 2 1 1 1 5 5 0
1 5 4 1 2 1 1 6 5 0
Картинка нарисовалась, но если я правильно понял, неопределённые клетки, как и пустые, помечаются точкой. Тогда ошибки там получаются в крайних рядах.
Странно, что ещё никто не написал приложение, которое разгадывает картинку, наведением камеры телефона на изображение в газете.
Флаг -O2 при компиляции
Флаг -O3 еще лучше.
Но вообще-то решение таких кроссвордов — это задача для SAT солвера.
Флаг -O3 еще лучше.
Не всегда. Почти все оптимизации компилятора эвристические, то есть некий дополнительный флаг (развернуть рекурсии, скрыть фреймы) в -O(x+1) по сравнению с -O(x) будет просто попыткой сделать программу более "оптимальной", но может иметь и обратный эффект. -O3 предполагается лучше -O2, как -O2 лучше -O1, это не значит что это будет правда работать быстрее на рандомной программе.
Довольно много вещей с -O2 работают быстрее чем с -O3, в т.ч. этот код. По-хорошему надо бы еще отдельные флаги оптимизации тестировать, чтобы затюнить быстродействие.
Но вообще-то решение таких кроссвордов — это задача для SAT солвера.
SAT солвер скушает быстро большой черно-белый кроссворд? Если не рассматривать цветные, для которых страшно генерировать конъюнктивную форму.
Пусть у нас есть K групп суммарно и кроссворд размером NxN, мы вычислили порядка KxN булевых переменных (для каждой группы все возможные позиции в его ряду) и состряпали формулу, она будет быстро считаться?
Может есть менее затратный способ составить формулу? Я к тому что если взять K=4 в среднем группы на ряд и N=50, выйдет 500'000 булевых переменных, которые будут считаться до Второго Пришествия.
Решение цветных японских кроссвордов со скоростью света