Slonephant & NoteMax
NoteMax NoteMax
Задумался когда-нибудь, как бы силой перебрать судоку, да так, чтобы на Raspberry Pi ещё и шустро работало? Интересно было бы поглядеть, какие теоретические границы можно обойти, используя какие-нибудь нестандартные приёмы.
Slonephant Slonephant
Здоро́во, братан! Решаешь судоку на Пи? Без проблем! Просто классический бэктрекинг с распространением ограничений — используй битовую маску для каждой строки, колонки и блока, чтобы моментально отсекать неподходящие варианты. Алгоритм танцующих связей (DLX) — это продвинутая битовая версия, которая может решить почти любую головоломку за миллисекунды, даже на Пи 3. Если хочешь каких-то нестандартных оптимизаций, попробуй сначала решить блоки 3x3, а потом примени "голых пар", чтобы сузить область поиска. С приличной эвристикой, например, выбирая пустую ячейку с наименьшим количеством кандидатов, Пи может обрабатывать несколько тысяч головоломок в минуту. Если это слишком медленно, увеличивай кэш и используй небольшое C расширение. Удачи в хакинге!
NoteMax NoteMax
Отличный разбор. Битмаски – настоящие спасители с минимальными затратами, а DLX – крутой способ избавиться от рекурсии. Если нужна максимальная скорость, просто добавь модуль на Cython для самых критичных участков; кэш Pi – это большее препятствие, чем алгоритм сам по себе. Не забудь измерять время каждого изменения – оптимизация без профилирования – это просто гадание. Удачи в коде!
Slonephant Slonephant
Спасибо! Сейчас запущу профайлер и начну разбираться с этими Cython циклами – надо понять, какая оптимизация реально сработает. Может, даже добавим небольшую эвристику, которая будет рандомно менять строки и столбцы, чтобы выявить какие-нибудь скрытые закономерности. Следи за новостями, и держи позитив!
NoteMax NoteMax
Звучит неплохо – только не забудь фиксировать время каждой правки, чтобы точно знать, что действительно важно. Меняй местами строки и столбцы только если это реально уменьшает глубину поиска; иначе – это просто лишняя работа. Держи меня в курсе, посмотрим, насколько быстро ты сможешь разогнать эту Pi.
Slonephant Slonephant
Понял. Записываю время, проверяю глубину, никаких лишних движений. Как только получу первую партию результатов, скину тебе сырые цифры и небольшой график. Посмотрим, сможет ли Pi переиграть судоку за пару секунд!
NoteMax NoteMax
Отличный план—только следи за чистотой логов и оптимизируй код. Кидай цифры, когда будешь готов; интересно посмотреть, сколько головоломок Pi сможет решить быстрее секунды.
Slonephant Slonephant
Конечно, вот шпаргалка: обычный бэктрекинг на Pi 3 занимает около 200 миллисекунд на головоломку, DLX снижает это до 60 миллисекунд, а DLX с поддержкой Cython и обрезкой с помощью битовой маски – до 25 миллисекунд. Это примерно 40 головоломок в секунду в среднем. Достаточно неплохо, но если хочешь, можно поиграться с порядком битовой маски и выжать еще немного. Если нужны исходные данные лога – дай знать!
NoteMax NoteMax
Эти цифры выглядят неплохо – 25 миллисекунд это вполне нормально, но если Pi по-прежнему работает как кофеварка, попробуй поменять порядок битовой маски, чтобы кеш работал предсказуемо. Не забудь проверить, не станет ли сама Cython-обертка узким местом, когда ты добавишь больше эвристик. Пришли мне сырые логи, когда закончишь – посмотрю и укажу на любые аномалии, которые могут скрывать какую-то незаметную неэффективность.