Given a grid how can I determine if elements of a grid are all in a single region. In the below case is true because each element in the matrix has a neighbor.
Example1:
gridneighbours([[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[4,1],[4,2]]).
true.
However in my second example, Example2:
gridneighbours([[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[3,1],[4,1],[4,2]]).
false.
This is false because [3,1],[4,1],[4,2] are disjoint to the previous elements. Initially I tried using subset from Prolog to check for an existing element next to another by simply adding or subtracting from X or Y, however this doesn't work because elements of a split region would be next to each other. Also diagonals don't count as being next to each other.
Updated, added code: Here is what I got:
%Check right
neighbourcheck([X,Y|_],S) :- X1 is X + 1, subset([[X1,Y]],S).
%Check left
neighbourcheck([X,Y|_],S) :- X1 is X - 1, subset([[X1,Y]],S).
%Check Up
neighbourcheck([X,Y|_],S) :- Y1 is Y + 1, subset([[X,Y1]],S).
%Check Down
neighbourcheck([X,Y|_],S) :- Y1 is Y - 1, subset([[X,Y1]],S).
% Iterate through all sublists and check for neighbours
gridneighbour(S) :- forall(member(X,S), neighbourcheck(X,S)).
The reason why this doesn't work is because subset doesn't care if we have a match up with another element that is disjointed. i.e. [3,1] matches up with [4,1]. Running this code and using the examples above give:
A naive approach that works can be outlined as follows:
Region and the rest, Rest. At the beginning, you can pick any single point to belong to Region, and whatever remains is in Rest.Rest for a point that is a neighbor to any point in Region.
Rest to Region and repeatRest at the end, then this is not a region.Here is a simpler way to define neighbors/2:
neighbors([X1,Y1], [X2,Y2]) :-
abs(X1-X2) + abs(Y1-Y2) =:= 1.
You can look for a point in one list that is a neighbor of a point in another list by simply trying out every possible combination:
% add_to_region(+Region0, +Rest0, -Region, -Rest)
%% Look in Rest0 for a neighbor to Region0;
%% Region is Region0 with the neighbor,
%% Rest is Rest0 without it
add_to_region(Region, Rest0, [B|Region], Rest) :-
member(A, Region),
select(B, Rest0, Rest),
neighbors(A, B).
The call to member/2 picks each point in Region to A, by backtracking. The call to select/3 picks each point in Rest0 to B, with rest of the points in Rest. If the two points are neighbors, B is added to front of Region.
This will fail if there is no more neighbors to the current region in Rest, and succeed at least once if there are. You might want to call this with once(add_to_region(Region0, Rest0, Region, Rest)) so that you don't have unnecessary choice points. Using your examples:
?- once(
add_to_region(
[[1,1],[1,2],[1,3],[2,1]],
[[2,2],[2,3],[3,1],[4,1],[4,2]],
Region, Rest)).
Region = [[2, 2], [1, 1], [1, 2], [1, 3], [2, 1]],
Rest = [[2, 3], [3, 1], [4, 1], [4, 2]].
See how [2,2] was picked from Rest and added to Region.
?- add_to_region(
[[1,1],[1,2],[1,3],[1,4],[1,5],[1,6]],
[[3,1],[4,1],[4,2]],
Region, Rest).
false.
This fails because none of the points in Rest is a neighbor to any of the points in Region.
As explained above is definitely doable, but with a slight modification, we can have an algorithm that is much easier to implement in Prolog. It goes like this:
set_region_rest(+Set, -Region, -Rest)
ordset.To do the splitting, we will maintain one extra list. We will call it a list of Open nodes: nodes that we haven't explored yet. At the beginning, the first element of our input list is the only open node. The rest of the elements are passed as they are. The last two arguments, the Region, and the Rest, are the output arguments.
open_set_closed_rest(Open, Set, Closed, Rest)
To do this in Prolog, I will first clean up the coordinate representation.
It is a bit annoying that they come in lists of two: it is far less writing if we used for example a pair instead: [X,Y] ---> X-Y. To do this, I add this predicate:
xy(XY) :-
coordinates(C),
maplist([[X,Y], X-Y]>>true, C, XY).
xy([1-1,1-3,1-2]).
xy([1-2,2-1,2-2]).
xy([1-1, 1-2, 1-3, 1-4, 1-5,
2-1, 2-5,
3-1, 3-5,
4-1, 4-5,
5-1, 5-2, 5-3, 5-4, 5-5]).
xy([1-1, 1-2, 1-3, 1-4, 1-5,
2-1, 2-5,
3-1, 3-3, 3-5,
4-1, 4-5,
5-1, 5-2, 5-3, 5-4, 5-5]).
coordinates([[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[4,1],[4,2]]).
coordinates([[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[3,1],[4,1],[4,2]]).
(I also put 4 additional test sets!)
So with this, I get:
?- xy(XY).
XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, ... - ...] [write] % press 'w' here
XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, 4-2] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 3-1, 4-1, 4-2] ;
XY = [1-1, 1-3, 1-2] ;
XY = [1-2, 2-1, 2-2] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-3, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5].
Here is how one could try to write the above algorithms in code:
set_region_rest([A|As], Region, Rest) :-
sort([A|As], [B|Bs]),
open_set_closed_rest([B], Bs, Region, Rest).
This just sorted the input Set and split off the first element from it. The first element is the first coordinate pair in the Open set, the rest is the Set, then the output arguments.
Now, to split the Set into a Region and a Rest, we need to keep on growing the Region as long as we have coordinate pairs in the Open set. If the Open set is empty, this means our Region is complete, and the remaining Set is the Rest:
:- use_module(library(clpfd)).
open_set_closed_rest([], Rest, [], Rest).
To find out which neighbors of a coordinate are in the Set, we use ord_intersection/4, which gives us the neighbors in Set and the rest of Set at the same time.
NB: The 4 neighbor coordinates are listed sorted!
open_set_closed_rest([X-Y|As], Set, [X-Y|Closed0], Rest) :-
X0 #= X-1, X1 #= X + 1,
Y0 #= Y-1, Y1 #= Y + 1,
ord_intersection([X0-Y,X-Y0,X-Y1,X1-Y], Set, New, Set0),
append(New, As, Open),
open_set_closed_rest(Open, Set0, Closed0, Rest).
This is it. With this, I get the following 6 solutions:
?- xy(XY), set_region_rest(XY, Region, Rest).
XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, 4-2],
Region = [1-1, 1-2, 1-3, 2-3, 2-2, 2-1, 3-1, 4-1, 4-2],
Rest = [] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 3-1, 4-1, 4-2],
Region = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6],
Rest = [3-1, 4-1, 4-2] ;
XY = [1-1, 1-3, 1-2],
Region = [1-1, 1-2, 1-3],
Rest = [] ;
XY = [1-2, 2-1, 2-2],
Region = [1-2, 2-2, 2-1],
Rest = [] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5],
Region = [1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5, 5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1],
Rest = [] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-3, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5],
Region = [1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5, 5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1],
Rest = [3-3].
By the way, using set_region_rest/3 as a building block, we can easily split a set of coordinates into regions:
set_regions([], []).
set_regions([X|Xs], [R|Rs]) :-
set_region_rest([X|Xs], R, Rest),
set_regions(Rest, Rs).
So now:
?- set_regions([1-1, 1-2, 1-3, 1-4, 1-5, 1-7,
2-1, 2-5, 2-7,
3-1, 3-3, 3-5, 3-7,
4-1, 4-5,
5-1, 5-2, 5-3, 5-4, 5-5, 5-7], R).
R = [[1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5,
5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1],
[1-7, 2-7, 3-7],
[3-3],
[5-7]].