Решатель головоломок - TreeNode Help

Question

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

Я бы предпочел не давать слишком много подробностей о головоломке.но игрок перемещается по сетке (скажем, 5 х 7), когда он движется, препятствия могут быть захвачены, поэтому необходимо отслеживать состояние доски.(это можно сделать в виде строки или массива)

Я понимаю, что мне нужно создать TreeNode, начиная с корня (начальная позиция игроков), и дать каждому узлу дочерние элементы возможных ходов, пока все возможныеходы рассчитаны.Тогда можно было собрать статистику головоломки.Количество возможных решений, минимальное количество ходов, которые нужно решить, среднее количество ходов, которые нужно решить, и т. Д.

У меня есть логика головоломки, которая будет возвращаться, если ходы возможны и тому подобное.У меня проблемы с созданием структуры TreeNode и проверкой того, чтобы ходы не дублировались.

Само приложение-головоломка находится на iPhone, но я пишу этот решатель / редактор на Mac.Любая помощь будет очень ценится.

Answer 1

Для обнаружения повторяющихся состояний вы должны поместить состояния в набор по мере их продвижения, а затем проверять каждый раз, когда находите новые состояния, чтобы увидеть, существуют ли они уже.Хотя, если проблема с пространством, вам придется прибегнуть только к проверке, не совпадают ли дочерние элементы с родительским, или к какой-то ограниченной версии этого подхода.

Класс узла очень прост.Он просто содержит указатель на родителя (если он есть) и переменную, которую он содержит (например, состояние).Возможно, вам также понадобятся другие переменные в зависимости от вашего приложения.

Когда вы попадаете на узел, вы используете функцию-преемник, чтобы получить оттуда все дочерние узлы (состояния, которые могут быть достигнуты за один ход) идобавить их в список.Вы выбираете из списка, чтобы пройти по дереву.

Answer 2

Возможно, вы могли бы сделать вариант рекурсии дерева ? Рекурсивно проходить по дереву, заставляя каждый конечный узел возвращать значение того, как трудно было туда добраться (если есть затраты, связанные с различными перемещениями), и описание того, как оно туда попало. Это, конечно, требует, чтобы игрок двигался только в одном направлении, иначе древовидная структура не описывает проблему. Немного больше информации о том, как выглядит ваша проблема, было бы полезно.

Это может быть сложный алгоритм, но он выполняет свою работу.