Решатель головоломок - Справка TreeNode

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

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

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

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

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


macos iphone objective-c puzzle treenode
person Chris Young    schedule 31.08.2011    source источник
comment
Спасибо. Могу я уговорить кого-нибудь включить исходный код? Создать класс TreeNode легко, я согласен (нужно ли включать методы или только свойства?), Что касается рекурсивного кода и проверки наличия узла перед добавлением, на котором я застрял. Узел должен включать CGPoint (местоположение игрока), состояние доски, родительский узел и массив дочерних элементов. что-нибудь еще? Большое спасибо за помощь.   -  person Chris Young    schedule 31.08.2011

Ответы (2)


arrow_upward
1
arrow_downward

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

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

person Pocket Universe    schedule 31.08.2011

arrow_upward
1
arrow_downward

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

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

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

person BobTurbo    schedule 31.08.2011