Prolog - neighbours in matrix

Question

I need a query, which help me resolve following problem:

I have list of coordinates [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]

(1,1) (1,2) (1,3)
(3,1) (3,2) (3,3)

I want get all possibilities of neighbours configurations in matrix

?- [((1,1), (2,1)), ((1,2), (2,2)), ((1,3), (2,3))];
?- [((1,1), (1,2)), ((2,1), (2,2)), ((1,3), (2,3))];
?- [((1,1), (2,2)), ((1,3), (2,1)), ((1,3), (2,3))];
?- [((1,1), (2,1)), ((1,2), (1,3)), ((2,2), (2,3))];
?- [((1,1), (2,1)), ((1,2), (2,3)), ((1,3), (2,2))];
?- false.

EDIT:

My try:

sublist([], _).
sublist([X|XS], [X|XSS]) :- 
        sublist(XS, XSS).
sublist([X|XS], [_|XSS]) :- 
        sublist([X|XS], XSS).

neighbour((X, Y), Rows, Columns, (X1, Y1)):- 
        between(1, Rows, X1), 
        abs(X1 - X) =< 1, 
        between(1, Columns, Y1), 
        abs(Y1 - Y) =< 1,
        \+ (X, Y) = (X1, Y1).

get_configuration([], _, _, _, []).
get_configuration([Head|Tail], Used, Rows, Columns, [(Head, Neighbour)|Tail2]) :- 
        neighbour(Head, Rows, Columns, Neighbour),
        \+ member(Neighbour, Used),
        append(Used, [Neighbour], Used2),
        get_configuration(Tail, Used2, Rows, Columns, Tail2).



gen(CountOfCoords, Coords, Rows, Columns, Result) :-
        CountOfPairs is CountOfCoords / 2,
        length(List, CountOfPairs),
        sublist(List, Coords),
        get_configuration(List, List, Rows, Columns, Result).

% ?- gen(6, [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)], 2, 3, X).

My second try:

ngbs(X) :- X = [((1,1),[(1,2),(2,1),(2,2)]),
                ((1,2),[(1,1),(1,3),(2,1),(2,2),(2,3)]),
                ((1,3),[(1,2),(2,2),(2,3)]),
                ((2,2),[(1,1),(1,2),(1,3),(2,1),(2,3)]),
                ((2,1),[(1,1),(1,2),(2,2)]),
                ((2,3),[(1,2),(1,3),(2,2)])].

generate(_, [], _, []).
generate([(Coord, Ngbs)|Tail], [_, _|Tail2], Used, [(Coord, Ngb)|Tail3]) :- 
    \+ member(Coord, Used),
    nth1(_, Ngbs, Ngb),
    \+ member(Ngb, Used),
    append(Used, [Coord, Ngb], Used2),
    generate(Tail, Tail2, Used2, Tail3).

generate(List, Result) :- 
    generate(List, List, [], Result).

% ngbs(X),generate(X, Y).

EDIT 2:

I have a data which might look like [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)] (*) (list of coordinates in board) or

[((1,1),[(1,2),(2,1),(2,2)]),
 ((1,2),[(1,1),(1,3),(2,1),(2,2),(2,3)]),
 ((1,3),[(1,2),(2,2),(2,3)]),
 ((2,2),[(1,1),(1,2),(1,3),(2,1),(2,3)]),
 ((2,1),[(1,1),(1,2),(2,2)]),
 ((2,3),[(1,2),(1,3),(2,2)])]

(list of pairs where the first element in the pair is a coordinate and the second is list of its neighbours) (*).

I try explain you what I really need (look at my second try in post) : )

http://i.stack.imgur.com/IapM2.jpg

Representation of first table: [((1,1), (2,1)), ((1,2), (2,2)), ((1,3), (2,3))].
second: [((1,1), (1,2)), ((2,1), (2,2)), ((1,3), (2,3))].
third: [((1,1), (2,1)), ((1,2), (1,3)), ((2,2), (2,3))].
fourth: [((1,1), (2,2)), ((1,2), (2,1)), ((1,3), (2,3))].
fifth: [((1,1), (2,1)), ((1,2), (2,3)), ((1,3), (2,2))].
which I can get calls list_of_neighbours(X) where X is one of (*).

Of course, but I have no idea how can I do it correctly. pastebin.com/00nbYyww — user2348332
Please incorporate your code into your question. Pastebins are ephemeral but your question is eternal. — Daniel Lyons

CapelliC CapelliC · Accepted Answer · 2013-05-04T07:03:58

I hope I understand the requirements. This snippet

neighbours(Cs, NBs) :-
    findall((C,NBsC),
        (select(C, Cs, Rs),
         findall(NB,
             (member(NB, Rs),
              neighbour(C, NB)
             ), NBsC)
        ), NBs).

neighbour((A,B),(C,D)) :- once(
    A =:= C + 1 ;
    A =:= C - 1 ;
    B =:= D + 1 ;
    B =:= D - 1 ).

yields

?- neighbours([(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)], NBs),maplist(writeln,NBs).
(1,1),[ (1,2), (2,1), (2,2), (2,3)]
(1,2),[ (1,1), (1,3), (2,1), (2,2), (2,3)]
(1,3),[ (1,2), (2,1), (2,2), (2,3)]
(2,1),[ (1,1), (1,2), (1,3), (2,2)]
(2,2),[ (1,1), (1,2), (1,3), (2,1), (2,3)]
(2,3),[ (1,1), (1,2), (1,3), (2,2)]
NBs = [ ((1, 1), [ (1, 2), (2, 1), (2, 2), (2, 3)]), ((1, 2), [ (1, 1), (1, 3), (2, 1), (2, 2), (2, 3)]), ((1, 3), [ (1, 2), (2, 1), (2, 2), (2, 3)]), ((2, 1), [ (1, 1), (1, 2), (1, 3), (..., ...)]), ((2, 2), [ (1, 1), (1, 2), (..., ...)|...]), ((2, 3), [ (1, 1), (..., ...)|...])].

Prolog - neighbours in matrix

1 Answers