Крестики-нолики игровой граф дизайн?

Question

это общий вопрос моей домашней работы, я просто прошу идеи или псевдокод.

Предположим, я создаю игру в крестики-нолики с использованием C ++. У меня уже есть класс Node, который содержит данные члена const, представляющие текущее состояние игровой доски, и массив const указателей на другие узлы, который содержит каждое возможное состояние следующего шага. Таким образом, это будет ориентированный граф без дублированных узлов (каждый узел имеет свое уникальное игровое состояние.).

У меня возникла проблема, когда я пытаюсь создать такой график. Кажется, мне нужно использовать рекурсию, потому что все члены данных в классе Node являются константными, поэтому нет способа их изменить. И вряд ли мне удастся придумать хорошую идею для создания такого графа сразу без дублирования Node (я имею в виду, что сделать его деревом будет легко, но это тратит много времени и пространства). Может помочь одна вещь: я могу сравнивать два разных игровых состояния, и я не думаю, что мне разрешено использовать какой-либо шаблон кроме <set>.

Так что, если у кого-то есть какие-либо идеи по этому поводу, пожалуйста, напишите свою мысль или псевдокод. Спасибо

Answer 1

Я думаю, вам нужно проверить наличие:

std::set< Node > checked_node;

bool isNodeChecked( Node ){
    return checked_node.find( Node )!=checked_node.end();
}

Вам нужно перегрузить что-то вроде operator = и operator <, чтобы std::set работал на вашем class Node;

Также std::unordered_map может работать.

(Хотя, как мне кажется, состояние крестики-нолики может быть представлено неотрицательными целыми числами от 0 до 3 ^ 9. Таким образом, будет достаточно std :: set, но вам потребуются дополнительные функции кодирования-декодирования .