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