Я хочу обнаружить цикл в неориентированном графе и вернуть true или false.Мой узел - это пара (X, Y) координат на столе.
У меня есть игра, которая играет в сетку крестики-нолики.Квант предиката (pos (X, Y), pos (Z, T), Color) напоминает кусок в моей сетке.Его можно поставить на две ячейки на моем столе 3х3.У меня может быть два квантовых положения из разных частей в одной и той же ячейке, и иногда они могут образовывать цикл, и я хочу его обнаружить.
Поскольку мои узлы - это ячейки (кортеж координат X, Y), мой кванткусок действует как ребро между двумя узлами.Я думал о том, чтобы получить все свои квантовые кусочки из состояния и сформировать список (DirectedEdges) пар ячеек, созданный первым findall.Мой график не направлен, поэтому я создал ReverseEdges и объединил их оба, чтобы получить список ненаправленных ребер.
Моя функция цикла не работает на моем неориентированном графе, и я не понимаю почему.Я не думаю, что мне нужно было добавлять столько контекста, чтобы задать свой вопрос.
Параметры цикла: Node - это отправная точка (первый параметр), Next перебирает график (второй параметр)., Visited - это список посещенных узлов (третий параметр), а Edges - список, который содержит все ребра моего графика (четвертый параметр).
EDIT: State - это список фигур на моей доске, он можетиметь больше или меньше штук.
State = [квант (pos (1, 1), pos (3, 1), белый), квант (pos (1, 2), pos (3, 2), черный), квантовый (pos (1, 1), pos (3, 2), белый)]
State = [квант (pos (1, 1), pos (3, 1), белый)квантовый (pos (1, 2), pos (3, 2), черный), квантовый (pos (1, 1), pos (3, 2), белый), квантовый (pos (1, 2), pos (3, 1), чёрный)].
Для первого состояния я хочу, чтобы has_cycle (State) вернул false, потому что у него нет цикла, и true для второго состояния.Цвет не мешает циклу.
cycle(Node, Node, _, _) :- !, true.
cycle(_, Node, Visited, _) :- member(Node, Visited), !, fail.
cycle(Node, Next, Visited, Edges) :- member((Next, NextNext), Edges), cycle(Node, NextNext, [Next|Visited], Edges).
has_cycle(State) :-
findall((pos(X, Y), pos(Z, T)), member(quantum(pos(X, Y), pos(Z, T), _), State), DirectedEdges),
findall((pos(X, Y), pos(Z, T)), member((pos(Z, T), pos(X, Y)), DirectedEdges), ReverseEdges),
append(DirectedEdges, ReverseEdges, Edges),
member((Node, Next), Edges),
cycle(Node, Next, [Next], Edges).