prolog - 用 prolog 解决 Numberlink 难题

Question

我有一个作业似乎超出了我的类(class)范围(我这么说是因为他们几乎没有教我们任何有关 prolog 的内容)，我必须编写一个 prolog 程序来解决 android 上的游戏“Flow Free”。在作业中它被称为 Numberlink。我可以在一个小时内用 C++ 解决这个问题，但因为我不太熟悉序言，所以它给我带来了麻烦。这就是我想做的:

1. 创建一个包含 bool 值的列表，以指示它是否已被访问或使用。
2. 递归搜索从给定起点到终点的所有可能路径使用广度优先搜索找到最短的终点路径。
3. 我想从那里开始。

我的尝试包括在网上搜索如何制作列表。当然，序言在任何地方都没有很好的记录，所以我一头雾水并放弃了。一位 friend 告诉我使用 maplist，但我不明白如何使用它来制作包含我需要的列表。

提前致谢。

编辑:感谢您的链接，但我希望制作一个 2D 列表来代表正在玩的棋盘。函数看起来像这样:

makeList(大小，列表):-

其中 size 是一个整数，表示方形列表 ex 中一维的大小。 (7x7)。

Answer 1

这是@CapelliC 解决方案的实现。该代码是不言自明的。如果两个 block 相邻并且具有相同颜色，或者与另一个相同颜色的连接 block 相邻，则它们是连接的。 (我使用 X 和 Y 而不是行和列，这使得在最后编写条件有点困惑。)

在 SWI-Prolog 中求解

https://flowfreesolutions.com/solution/?game=flow&pack=green&set=5&level=1

connected(P1, P2, M, Visited) :-
    adjacent(P1, P2),
    maplist(dif(P2), Visited),
    color(P1, C, M),
    color(P2, C, M).
connected(P1, P2, M, Visited) :-
    adjacent(P1, P3),
    maplist(dif(P3), Visited),
    color(P1, C, M),
    color(P3, C, M),
    connected(P3, P2, M, [P3|Visited]).

adjacent(p(X,Y1), p(X,Y2)) :- Y2 is Y1+1.
adjacent(p(X,Y1), p(X,Y2)) :- Y2 is Y1-1.
adjacent(p(X1,Y), p(X2,Y)) :- X2 is X1+1.
adjacent(p(X1,Y), p(X2,Y)) :- X2 is X1-1.

color(p(X,Y), C, M) :-
    nth1(Y, M, R),
    nth1(X, R, C).

sol(M) :-
    M = [[1,_,_,_,1],
         [2,_,_,_,_],
         [3,4,_,4,_],
         [_,_,_,_,_],
         [3,2,5,_,5]],
    connected(p(1,1), p(5,1), M, [p(1,1)]),
    connected(p(1,2), p(2,5), M, [p(1,2)]),
    connected(p(1,3), p(1,5), M, [p(1,3)]),
    connected(p(2,3), p(4,3), M, [p(2,3)]),
    connected(p(3,5), p(5,5), M, [p(3,5)]).

示例查询:

?- sol(M).
M = [[1, 1, 1, 1, 1],
     [2, 2, 2, 2, 2], 
     [3, 4, 4, 4, 2],
     [3, 2, 2, 2, 2], 
     [3, 2, 5, 5, 5]].