Можно подтянуть откат, сделав порядок ходов более умным. Сначала используй правило Варнсдорфа: всегда выбирай клетку с наименьшим количеством возможных дальнейших ходов. Это простой эвристический метод, который значительно сокращает количество ветвей. Во-вторых, проведи небольшой просчет вперёд: перед тем, как сделать ход, посчитай, сколько ходов останется для каждой неисследованной клетки. Если у какой-то клетки окажется ноль возможных ходов, сразу откатывайся – это ранний тупик. Также можно отсекать симметричные решения. Если доска стандартная, зеркально отражай частичный путь и пропускай дубликаты. Веди битовой массив посещённых клеток, чтобы проверки ходов были за O(1). И если ты пишешь на языке, который это позволяет, кэшируй степени клеток по мере исследования; степень меняется только при посещении соседа, так что можно обновлять её постепенно, а не пересчитывать заново. И наконец, старайся завершить полный тур сразу после того, как ты попадёшь в угол или край, которые загоняют тебя в ловушку. Эти позиции часто приводят к невозможным завершениям, поэтому ранний откат там экономит время.