Можно попробовать ввести в перебор ограничения, чтобы каждая следующая позиция вела к уменьшению количества беспорядков, а так же эта комбинация еще не посещалась.
Навскидку трудно сказать, но если делать перебор в ширину с запоминанием позиции, которые уже были, алгоритм выглядит достаточно простым и быстрым. Только может возникнуть проблема с памятью.
В начале мы сделали так же, но для пользователя достаточно долго ожидать старта игры, поэтому мы отказались от такого решения. Фишки просто перелетают сразу на позиции.
Достаточно одной фразы.