Теоретический способ решения этой проблемы состоит в том, чтобы представить каждую конфигурацию доски в качестве вершины графа, а затем использовать поиск в первом дыхании с отсечкой, основанный на чем-то вроде расстояния до Манхэттена, для получения кратчайшего пути от начальной конфигурации до решения.
Одна из проблем этого подхода заключается в том, что для любой доски n x n, где n > 3 игровое пространство становится настолько большим, что неясно, как можно эффективно отметить посещенные вершины. Другими словами, нет очевидного способа оценить, идентична ли текущая конфигурация платы той, которая была ранее обнаружена путем обхода какого-то другого пути. Другая проблема заключается в том, что размер графа растет так быстро с n (это приблизительно (n^2)!), что он просто не подходит для атаки методом грубой силы, поскольку число путей становится невозможным в вычислительном отношении для прохождения.
Эта статья Иана Парберри Алгоритм в реальном времени для (n^2 − 1) - Puzzle описывает простой жадный алгоритм, который итеративно приходит к решению путем заполнения первой строки, затем первого столбца, затем второй ряд ... Решение приходит почти сразу, однако решение далеко от оптимального; по сути, это решает проблему так, как это делает человек, не используя никаких вычислительных мышц.
Эта проблема тесно связана с проблемой решения кубика Рубика. График всех игр показывает, что он слишком велик, чтобы его можно было решить с помощью грубой силы, но есть довольно простой 7-шаговый метод, который может быть использован для решения любого куба за 1-2 минуты ловким человеком. Этот путь, конечно, не оптимален. Научившись распознавать паттерны, которые определяют последовательности движений, скорость можно снизить до 17 секунд . Однако этот подвиг Иржи несколько сверхчеловеческий!
Метод, описанный Parberry, перемещает только одну плитку за раз; Можно предположить, что алгоритм можно улучшить, используя ловкость Джири и перемещая несколько плиток одновременно. Это, как доказывает Парберри, не уменьшит длину пути с n^3, но уменьшит коэффициент ведущего члена.