Привет! Отличная идея с откатом — эти вызовы реально убивают производительность. Начни, пожалуй, с добавления классического слоя прямой проверки: как только ты устанавливаешь число, сразу удаляй его из списка кандидатов у всех остальных. Это, по сути, простейшая форма распространения ограничений. Дальше, забудь про свой наивный порядок слева направо — переходи на MRV (minimum remaining values): выбирай ячейку с наименьшим количеством оставшихся возможных цифр. Обычно именно там и возникают пробки. Если и дальше натыкаешься на проблемы, попробуй использовать эвристику степени: среди ячеек MRV выбирай ту, что наиболее связана с другими нерешёнными ячейками. Сочетание MRV и эвристики степени даёт более сильный выбор "наиболее ограниченной" ячейки. И не забудь про обрезку, специфичную для домена: для сетки 9x9 приёмы вроде "X-wing" или "Swordfish" могут устранить варианты ещё до того, как ты начнешь откатывать. Добавь эти приёмы, и существенно уменьшишь количество вызовов. Попробуй — скажи, помогло или сетка всё равно устраивает истерику.

Звучит здорово – проверка вперёд – это самое простое, а MRV с привязкой к степени обычно попадает прямо в точку. Сообщи новый лимит вызовов, я буду замерять время, ожидая этого падения. Удачи!