使用 Prolog 查找网格中同一行和同一列中的重复项

Question

我是 Prolog 新手。我正在编写 Prolog 代码来解决一个难题，该难题需要我在二维数字网格中查找重复项。

我的输入类似于：

grid(1,1,1).
grid(2,1,2).
grid(2,1,3).
grid(5,1,4).
grid(3,2,1).
grid(4,2,2).
grid(5,2,3).
grid(9,2,4).
grid(6,3,1).
grid(7,3,2).
grid(2,3,3).
grid(8,3,4).
grid(4,4,1).
grid(5,4,2).
grid(1,4,3).
grid(3,4,4).

代表矩阵：

1 2 2 5
3 4 5 9
6 7 2 8
4 5 1 3

我尝试的代码类似于：

finddup(N,X,Y):-
        a is X, b is Y,
        print('Rule 1 \n'),
        ((grid(N,U,1), U \= a, print('U->'), write(U), print('\n'), print('X->'), write(a));
        (grid(N,1,U), U \= b, print('U->'), write(U), print('\n'), print('Y->'), write(b));
        (grid(N,U,4), U \= a, print('U->'), write(U), print('\n'), print('X->'), write(a));
        grid(N,4,U), U \= b, print('U->'), write(U), print('\n'), print('Y->'), write(b)));
        print('Rule 2 \n'),
        ((finddup(N,X-1,Y), X-1 >= 1, X-1 =< 4, Y >= 1, Y =< 4);
        (finddup(N,X+1,Y), X+1 >= 1, X+1 =< 4, Y >= 1, Y =< 4);
        (finddup(N,X,Y-1), X >= 1, X =< 4, Y-1 >= 1, Y-1 =< 4);
        (finddup(N,X,Y+1), X >= 1, X =< 4, Y+1 >= 1, Y+1 =< 4)).

请帮助我...我从一两周以来一直在尝试这个...

谢谢，
维卡斯

Answer 1

您不需要尝试指定行索引和列索引的范围，因为它们已经在 grid(..) 事实中明确给出。只需让 Prolog 回溯这些值即可。

finddup(N,R,C) :-
    grid(N,R,C),
    grid(N,R,C2), C \= C2,
    grid(N,R2,C), R \= R2.

grid(N,R,C) 将验证给定值是否在网格中，或者如果 N、R、C 中的任何一个（或全部）没有值，它将回溯所有可能的组合。

grid(N,R,C2), C \= C2, 会在同一行中找到具有相同 N 的另一列。

对于 grid(N,R2,C), R 也是如此\= R2 - 但对于另一行。

这将为它找到的任何重复项返回 true，但之后可能返回 false，因为最后一次回溯可能会失败。例如：（

?- finddup(N,R,C).
N = 2,
R = 1,
C = 3 ;
false.

?- finddup(2,1,3).
true ;
false.

?- 

其中分号是用户输入）

您可以在末尾添加一个剪切，以在找到解决方案后停止任何进一步的回溯：

finddup(N,R,C) :-
    grid(N,R,C),
    grid(N,R,C2), C \= C2,
    grid(N,R2,C), R \= R2, !.

给出

?- finddup(N,R,C).
N = 2,
R = 1,
C = 3.

?- finddup(2,1,3).
true.

?-