How can I determine that all given matrix coordinates are connected?

Question

Given the grid, how to determine whether all grid elements are in the same area. In the case below, it is true, because each element in the matrix has a neighboring element.

Example 1:

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 not true because [3,1], [4,1], [4,2] do not overlap with the previous elements. At first I tried to use a subset of Prolog to check an existing element next to another, simply adding or subtracting from X or Y, however this does not work because the elements of the divided area will be next to each other. Also, diagonals are not considered 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 this does not work is because the subset does not care about whether we are matched with another element that is not related. those. [3.1] corresponds to [4.1]. Running this code and using the above examples gives:

• Example 1: True
• Example2: True (obviously, this should be wrong, because [3,1], [4,1] and [4,2] are separate).

Answer 1

A naive approach that works can be described as follows:

• Start with two sets (lists?) Of points: those that are known to belong to the region, Region , and the rest, Rest . First, you can select any point that should belong to Region , and all that remains is in Rest .
• See Rest for a point that is a neighbor of any point in a Region.
  • if you find a neighbor, move it from Rest to Region and repeat
  • If you have not found a neighbor, stop
• If at the end there are dots in Rest , this is not a region.

Here is an easier way to define neighbors/2 :

 neighbors([X1,Y1], [X2,Y2]) :- abs(X1-X2) + abs(Y1-Y2) =:= 1. 

You can find a point in one list that is a neighbor of a point in another list, just try any 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). 

A call to member / 2 selects each point in the region by A, by backtracking. A call to select / 3 selects each point in Rest0 for B, and the remaining points in Rest. If two points are neighbors, B is added to the front of the region.

This will not succeed if there are no more neighbors with the current region in Rest and succeed at least once, if any. You can call it with once(add_to_region(Region0, Rest0, Region, Rest)) so that you don't have unnecessary selection 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 selected 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 is not done because none of the points in Rest is adjacent to any of the points in Region .

Edit

As explained above, it is definitely doable, but with a little modification, we can have an algorithm that is much easier to implement in Prolog. This happens as follows:

set_region_rest(+Set, -Region, -Rest)

• Sort a set of points to the standard order of terms; you now have an ordset .
• Divide this set into a region and Rest that does not belong to it.

To do the splitting, we will save one additional list. We will call it the list of Open nodes: nodes that we have not yet studied. First, the first element of our input list is the only open node. The remaining elements are transmitted as they are. The last two arguments: the region and the rest, are the output arguments.

open_set_closed_rest(Open, Set, Closed, Rest)

• If the Open set is empty, then the rest of the closed set (now Region); the rest Set - Rest.
• Otherwise:
  • Take the first pair of coordinates from the open list; immediately place it in front of the closed coordinates.
  • Try to find any of the neighbors of these first pairs in the coordinate set; if you find them, add them to the front of the Open set; the rest of Set after deleting neighbors is the new Set.
  • Try again with the new Open set, the rest of the private set, the remaining set, and Rest.

To do this in Prolog, I will first clear the coordinate view. It’s a little annoying that they are included in the lists of two: it’s much less write if we used the pair instead: [X,Y] ---> XY . To do this, I add this predicate:

 xy(XY) :- coordinates(C), maplist([[X,Y], XY]>>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 added 4 additional test suites!)

So 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's how to 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). 

It just sorted the Set input and separated the first element from it. The first element is the first coordinate pair in the Open set, the rest is Set, then the output arguments.

Now, to split Set into Region and Rest, we need to continue to grow Region, if we have coordinate pairs in the Open set. If the Open set is empty, this means that our region is completed, and the remaining Set is Rest:

 :- use_module(library(clpfd)). open_set_closed_rest([], Rest, [], Rest). 

To find out which neighboring coordinates are in the set, we use ord_intersection/4 , which gives us the neighbors in Set and the rest of the set at the same time.

NB : 4 neighboring coordinates mapped!

 open_set_closed_rest([XY|As], Set, [XY|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). 

It is he. In doing so, 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 the 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]]. 

Answer 2

This problem can be considered as an instance of connection search algorithms . Such algorithms often use a special data structure, which basically serves the following two purposes:

 1) For a point p, find a representant p* in the data structure 2) For two representants p1* and p2* extend the data structure by connecting both 

Here is a Prolog implementation that uses the local fact / 2 associated with the stream as the union finds the data structure. Here is an example for the second grid problem:

 ?- regions(L). L = [(1, 6), (4, 2)]. 

Technical note: the union Prolog also has a built-in connection search component, if you specify the variable X, it will be dereferenced, which will be step 1). If you combine X = Y and X and Y are already dereferenced, one variable will be bound to another, which is step 2).