一种有效的简单方法可以概述如下：
- 从两组点（列表？）开始：您知道属于某个区域的点，
Region其余的，Rest。一开始，你可以选择任意一个点属于Region，剩下的就在Rest.
- Look in
Rest for a point that is a neighbor to any point in Region.
- 如果你找到邻居，请将其从
Rest to Region并重复
- 如果你找不到邻居，就停下来
- 如果有点在
Rest最后，那么这就是not一个地区。
这是一个更简单的定义方法neighbors/2:
neighbors([X1,Y1], [X2,Y2]) :-
abs(X1-X2) + abs(Y1-Y2) =:= 1.
您可以通过简单地尝试每种可能的组合来查找一个列表中与另一个列表中的点相邻的点：
% 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).
对member/2 的调用通过回溯来选取Region 中的每个点到A。对 select/3 的调用选择 Rest0 到 B 中的每个点，其余点在 Rest 中。如果两个点是邻居，则将 B 添加到 Region 前面。
如果当前区域没有更多邻居，则此操作将会失败Rest，并且如果有的话至少成功一次。你可能想用once(add_to_region(Region0, Rest0, Region, Rest))这样你就没有不必要的选择点。使用你的例子：
?- 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]被挑选自Rest并添加到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.
这失败了，因为没有任何点Rest是任意点的邻居Region.
Edit
如上所述，这绝对是可行的，但只需稍加修改，我们就可以拥有一个更容易在 Prolog 中实现的算法。事情是这样的：
set_region_rest(+Set, -Region, -Rest)
- 按照标准术语顺序对点集进行排序；现在你有一个
ordset.
- 将此集合拆分为一个 Region 和一个不属于它的 Rest
为了进行拆分，我们将维护一个额外的列表。我们将其称为开放节点列表：我们尚未探索的节点。一开始，输入列表的第一个元素是唯一的开放节点。
其余元素按原样传递。
最后两个参数 Region 和 Rest 是输出参数。
open_set_closed_rest(Open, Set, Closed, Rest)
- 如果开放集为空，则封闭集的其余部分（现在的区域）也为空；剩下的 Set 就是 Rest。
- Otherwise:
- 从Open列表中取出第一对坐标；立即将其放在 Closed 坐标的前面。
- 尝试在坐标集中找到第一对的任何邻居；如果找到任何，请将其附加到公开组的前面；删除邻居后剩下的 Set 是新的 Set。
- 用新的公开组、剩余的封闭组、剩余的组和休息组再试一次。
为了在 Prolog 中做到这一点，我将首先清理坐标表示。
有点烦人的是，它们出现在两个列表中：如果我们使用一对来代替，那么书写就会少得多：[X,Y] ---> X-Y。为此，我添加此谓词：
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]]).
（我还添加了 4 个额外的测试集！）
有了这个，我得到：
?- 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].
以下是尝试用代码编写上述算法的方法：
set_region_rest([A|As], Region, Rest) :-
sort([A|As], [B|Bs]),
open_set_closed_rest([B], Bs, Region, Rest).
这只是对输入 Set 进行排序并从中分离出第一个元素。
第一个元素是 Open 集中的第一个坐标对，其余的是 Set，然后是输出参数。
现在，为了将集合分成区域和休息，只要我们在开放集中有坐标对，我们就需要继续增长区域。如果Open集是空的，这意味着我们的Region是完整的，剩下的Set就是Rest：
:- use_module(library(clpfd)).
open_set_closed_rest([], Rest, [], Rest).
为了找出集合中坐标的哪些邻居，我们使用ord_intersection/4 http://eu.swi-prolog.org/pldoc/doc_for?object=ord_intersection/4，它同时为我们提供了 Set 中的邻居以及 Set 的其余部分。
NB：4个邻居坐标已排序！
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).
就是这个。有了这个，我得到了以下6种解决方案：
?- 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].
顺便说一下，使用set_region_rest/3作为构建块，我们可以轻松地将一组坐标分割为区域：
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]].
