В статье в Википедии, на которую вы ссылаетесь, уже упоминается, что существует всего 3 626 632 возможных позиций на доске, поэтому любому современному компьютеру легко выполнить исчерпывающий поиск пространства.
Ваш алгоритм, приведенный выше, верен, уловка заключается в том, чтобы реализовать «не видел вращения или переворота этой доски раньше», что вы можете сделать, используя хеш-таблицу. Вам, вероятно, не нужна строка «отменить перемещение», поскольку реальная реализация передаст состояние платы в качестве аргумента рекурсивному вызову, поэтому вы будете использовать стек для хранения состояния.
Кроме того, неясно, что вы можете подразумевать под «эффективными».
Если вы хотите найти все последовательности ходов, которые приводят к выигрышному этапу, вам нужно провести исчерпывающий поиск.
Если вы хотите найти самую короткую последовательность, вы можете использовать алгоритм ветвления и ограничения, чтобы на ранних этапах отрезать некоторые деревья поиска. Если вы можете придумать хорошую статическую эвристику, то можете попробовать A * или один из его вариантов.