Программирование головоломки - невозможно для оптимизации?

Я писал программы для решения различных числовых задач, но я постоянно разрабатываю необоснованно сложные алгоритмы поиска, которые я не могу оптимизировать.

Например, в одной головоломке вам дана сетка 3x3 чисел от 1 до 9 ниже:

123
456
789

Вы можете циклически перемещать числа в любой строке или столбце в любом направлении. Ниже приведен пример смещения верхней строки чисел вправо . Цифры будут повторяться, если они находятся на краю сетки.

123 -> 312
456    456
789    789

Вы должны перемещать числа таким образом, пока не создадите магический квадрат , в котором сумма чисел в каждом столбце, строке и диагонали равна 15.

Я написал DFS. алгоритм грубой силы для проверки всех возможных последовательностей ходов, хотя количество доступных ходов на каждом ходу увеличивается экспоненциально (примерно 12 ^ [текущий ход]), что делает его бесполезным.

Кажется, что BFS будет оптимальным решением для поиска правильных ходов, но для этого мне потребовалось бы хранить сотни, если не тысячи копий сетки, чтобы вернуться назад!

Я постоянно сталкиваюсь с такими проблемами. Алгоритмы BFS и DFS используют слишком много памяти и времени соответственно. Мне нужна помощь в оптимизации подобных алгоритмов, чтобы они работали быстрее и эффективнее. Может быть, поможет распознавание закономерностей и соотношений чисел или предоставление логике алгоритма для достижения цели? (Я не знаю, что это повлечет за собой).

РЕДАКТИРОВАТЬ:

Мой фиксированный алгоритм работает как шарм. Было очень важно научиться нумеровать мои перестановки. Спасибо вам всем!