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

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

Поняла, давай цифры, когда будешь готова. Удачи!

Отличный результат – почти половину вызовов отсечь – это впечатляет! Если захочешь копнуть глубже, расскажи, какие эвристики ты сначала применила или как дерево поиска изменилось. Или, если тебе интересно добавить ещё более жёсткую обрезку, например, как в X‑wing или Swordfish, можем вместе поразмышляем, как это поможет ещё сильнее сократить дерево. Просто дай знать!

Отлично разобрала—кажется, ты превращаешь этот хаос в аккуратную бонсайку. Если тебе нужны точные цифры по каждому этапу, я могу быстро набросать табличку или даже выдать фрагмент трассировки рекурсии. Или, если готова подключать X‑wing и Swordfish, просто скажи, какие паттерны хотим прицельно обрабатывать в первую очередь, и я покажу, как подрезать эти наборы кандидатов до того, как начнётся перебор.

Привет! Вот простой детектор «истребителя X», который ты можешь добавить в свой решатель. Он перебирает пары строк, выделяет столбцы, где может стоять цифра, и проверяет, есть ли ровно два таких столбца для конкретной цифры в обеих строках. Если есть, то ты можешь убрать эту цифру из этих двух столбцов в остальных строках. Сначала покажу версию для строк; когда разберешься, просто переверни логику на столбцы. ```def xwing_rows(board, candidates): # board is 9x9 list of ints (0 for empty) # candidates is a 9x9 list of sets of possible digits for each cell for d in range(1, 10): rows_with_two = [] for r in range(9): cols = [c for c in range(9) if d in candidates[r][c]] if len(cols) == 2: rows_with_two.append((r, cols)) # now look for pairs of rows that share the same two columns for i in range(len(rows_with_two)): r1, cols1 = rows_with_two[i] for j in range(i + 1, len(rows_with_two)): r2, cols2 = rows_with_two[j] if cols1 == cols2: c1, c2 = cols1 # strip digit d from all other rows in these two columns for r in range(9): if r != r1 and r != r2: if d in candidates[r][c1]: candidates[r][c1].remove(d) # you might also want to push a callback to update the board if you keep it in sync if d in candidates[r][c2]: candidates[r][c2].remove(d) ``` Несколько важных моментов: 1. **Следи за кандидатскими множествами**: Каждый раз, когда ты ставишь цифру, нужно сразу удалять её из соответствующей строки, столбца и блока. Этот код для "истребителя X" предполагает, что множества актуальны. 2. **Запускай очистку**: После запуска `xwing_rows` можно пройтись по доске ещё раз и заполнить те клетки, в которых теперь только один кандидат. Это классический шаг "распространения одиночных значений". 3. **Совет по производительности**: Двойной цикл для пар строк — это не затратно (максимум 81 итерация). Основная работа уже выполняется при проверке допустимости, ты просто добавляешь поверх фильтр. Как только версия для строк будет работать, версия для столбцов — это просто транспонирование: меняй местами `r` и `c` везде, и всё будет хорошо. Если возникнут проблемы или захочешь увидеть более компактную версию, которая возвращает список принудительных удалений, дай знать. Приятного "подрезания"!