Проверьте, не смежны ли списки матричных индексов - PullRequest
Новая
       33

Проверьте, не смежны ли списки матричных индексов

0 голосов
/ 11 декабря 2018

Учитывая список индексов List и размер матрицы N, я хочу проверить, являются ли индексы этого списка смежными.

Например, матрица 5x5, индексы выглядят следующим образом: 

 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25


isContiguous([11,12,13,7,2], 5) :- yes.

isContiguous([14,15,16,17,18], 5) :- no.

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

Спасибо за ваше время:)

1 Ответ

0 голосов
/ 11 декабря 2018

Вы можете определить отношение для смежности узлов и процедуру, чтобы увидеть, существует ли один связанный граф между вашими узлами: 

:-use_module(library(clpfd)).

adjacent(Size, N, _, Adj):-
  Adj #= N-Size,
  Adj #> 0.
adjacent(Size, N, Max, Adj):-
  Adj #= N+Size,
  Adj #=< Max.
adjacent(Size, N, _, Adj):-
  0 #\= N mod Size,
  Adj #= N+1.
adjacent(Size, N, _, Adj):-
  1 #\= N mod Size,
  Adj #= N-1.

is_contiguous(L, Size):-
  Max #= Size*Size,
  between(1, Max, Len), % sanity checks for when L is not instantiated
  length(L, Len),
  select(N, L, L1),
  between(1, Max, N),   % idem
  is_contiguous1([N], L1, Size, Max).

is_contiguous1(_, [], _, _).
is_contiguous1(Seen, Rem, Size, Max):-
  member(N, Seen),
  adjacent(Size, N, Max, Adj),
  \+(member(Adj, Seen)),
  select(Adj, Rem, NRem),
  is_contiguous1([Adj|Seen], NRem, Size, Max).

Пример выполнения: 

?- is_contiguous([11,12,13,7,2], 5).
true.
?- is_contiguous([14,15,16,17,18], 5).
false.
?- once(is_contiguous([14,15,X,16,17,18], 5)).
X = 19
...