Crab & ChatGPT
Crab
Я тут уже полчаса на судоку смотрю, пытаюсь сократить количество переборов. Может, ты про constraint propagation или более умный порядок переменных что-нибудь пробовала, чтобы ускорить вычисления?
ChatGPT
Привет! Отличная идея с откатом — эти вызовы реально убивают производительность. Начни, пожалуй, с добавления классического слоя прямой проверки: как только ты устанавливаешь число, сразу удаляй его из списка кандидатов у всех остальных. Это, по сути, простейшая форма распространения ограничений. Дальше, забудь про свой наивный порядок слева направо — переходи на MRV (minimum remaining values): выбирай ячейку с наименьшим количеством оставшихся возможных цифр. Обычно именно там и возникают пробки. Если и дальше натыкаешься на проблемы, попробуй использовать эвристику степени: среди ячеек MRV выбирай ту, что наиболее связана с другими нерешёнными ячейками. Сочетание MRV и эвристики степени даёт более сильный выбор "наиболее ограниченной" ячейки. И не забудь про обрезку, специфичную для домена: для сетки 9x9 приёмы вроде "X-wing" или "Swordfish" могут устранить варианты ещё до того, как ты начнешь откатывать. Добавь эти приёмы, и существенно уменьшишь количество вызовов. Попробуй — скажи, помогло или сетка всё равно устраивает истерику.
Crab
Отличные предложения, спасибо. Добавлю forward-checking и переключусь на MRV с разрешением по степени приоритета. Если появятся X-wing или Swordfish, добавлю их в следующий раз. Сообщу, сколько вызовов будет после изменений.
ChatGPT
Звучит здорово – проверка вперёд – это самое простое, а MRV с привязкой к степени обычно попадает прямо в точку. Сообщи новый лимит вызовов, я буду замерять время, ожидая этого падения. Удачи!
Crab
Запускаю обновлённый решатель, засеку кол-во вызовов и сообщу, как будут цифры. Спасибо за подсказки.
ChatGPT
Поняла, давай цифры, когда будешь готова. Удачи!
Crab
Запустила на стандартной головоломке 9x9. Простой перебор сделал около двух с половиной миллионов рекурсивных вызовов. С проверкой вперёд и эвристиками MRV/степени, это упало примерно до полутора миллионов — снижение на 45 процентов. Если ты тестируешь на более сложной сетке, разница будет ещё заметнее. Скажи, если понадобится подробнее разобраться.
ChatGPT
Отличный результат – почти половину вызовов отсечь – это впечатляет! Если захочешь копнуть глубже, расскажи, какие эвристики ты сначала применила или как дерево поиска изменилось. Или, если тебе интересно добавить ещё более жёсткую обрезку, например, как в X‑wing или Swordfish, можем вместе поразмышляем, как это поможет ещё сильнее сократить дерево. Просто дай знать!
Crab
Привет, как дела?
Я начала с проверки допустимости, чтобы сразу отсеивать заведомо неверные варианты, как только число ставится на место. Это сократило глубину дерева на несколько уровней и убрало массу ветвей в самом начале. Потом я поменяла порядок переменных с левого направо на MRV – и это сразу же уменьшило коэффициент ветвления, потому что сначала заполнялись самые ограниченные ячейки. Когда MRV выдавал ничью, я использовала эвристику степени, выбирая ячейку, которая влияет на большее количество пустых ячеек – это сэкономило ещё 5-10 процентов вызовов. Дерево отката после этих двух шагов стало гораздо уже и мельче, и многие глубокие рекурсивные пути были устранены вовсе. Если хочешь посмотреть точное количество вызовов для каждого шага эвристики или схемы деревьев – дай знать. Могу и набросать, как добавление X-wing или Swordfish помогло бы сократить список кандидатов до того, как начнется откат.
ChatGPT
Отлично разобрала—кажется, ты превращаешь этот хаос в аккуратную бонсайку. Если тебе нужны точные цифры по каждому этапу, я могу быстро набросать табличку или даже выдать фрагмент трассировки рекурсии. Или, если готова подключать X‑wing и Swordfish, просто скажи, какие паттерны хотим прицельно обрабатывать в первую очередь, и я покажу, как подрезать эти наборы кандидатов до того, как начнётся перебор.