Prolog：不断得到错误的结果

Question

我正在尝试创建一个程序，它可以在 n * n 国际象棋上放置最多的骑士，而没有任何骑士吃掉另一个。我设法找到了解决方法，但是我一直得到错误的结果，而不是显示解决方案所在的列表。

:- use_module(library(lists), [member/2]).
:- use_module(contestlib, [for/3]).

genere(0,[]).
genere(N,[N|L]) :-
   N>0,
   N1 is N-1,
   genere(N1,L).

generePos(N,[(Lig,Col)]) :-
   genere(N,L),
   member(Lig,L),
   member(Col,L).

genereEchiquier(N,PlacedKnights) :-
   findall((X,Y),(for(X,1,N),for(Y,1,N)),PlacedKnights).

knights(N) :-
    genereEchiquier(N,PlacedKnights),
    generePos(N,P1),
    knighta(P1,PlacedKnights).

knighta([(X,Y)|_],[]) :-
   write("No solution, next sol").
knighta([(X,Y)|_],[_|PlacedKnights]) :-
   (  is_attacked(X,Y,PlacedKnights)
   -> knights(P1,PlacedKnights)
   ;  write([(X,Y)|PlacedKnights)!
   ).

is_attacked(X,Y,PlacedKnights) :-
    ( NX is X - 1, NY is Y - 2
    ; NX is X - 1, NY is Y + 2
    ; NX is X + 1, NY is Y - 2
    ; NX is X + 1, NY is Y + 2
    ; NX is X - 2, NY is Y - 1
    ; NX is X - 2, NY is Y + 1
    ; NX is X + 2, NY is Y - 1
    ; NX is X + 2, NY is Y + 1
    ),
    member((NX,NY),PlacedKnights).

当我运行程序处于调试模式时，行 knighta(P1,PlacedKnights)。没有把节目带到 knighta/2 ：这里

knighta([(X,Y)|_],[_|PlacedKnights])

我不知道为什么。

Answer 1

首先，您的代码存在一些问题：

首先，我建议您缩进代码；
你应该使用 ] 而不是 !;
你有时会在应该是 knighta 的地方调用 knights；和
你应该先在 is_attached 中的约束之前使用 member。

也许您应该考虑彻底重新设计。

首先，您可以将以下内容用作 is_attacked 谓词：

is_attacked(X,Y,PlacedKnights) :-
    member((NX,NY),PlacedKnights),
    is_attacked(X,Y,NX,NY).

is_attacked(XA,YA,XB,YB) :-
    DX is abs(XA-XB),
    DY is abs(YA-YB),
    is_attacked(DX,DY).

is_attacked(1,2).
is_attacked(2,1).

因此，您遍历所有已经放置的骑士，然后计算差异并检查它是 (2,1) 还是 (1,2) 差异。

接下来您可以使用以下谓词生成所有可能的配置：

generateSolution(R,_,R).
generateSolution(Q,N,R) :-
    for(X,1,N),
    for(Y,1,N),
    \+ member((X,Y),Q),
    \+ is_attacked(X,Y,Q),
    generateSolution([(X,Y)|Q],N,R).

其中 generateSolution(L,N,R) 是一个谓词，其中 L 已经放置的马，N 棋盘的大小和 R 已经给出的马的任何配置正确（注意这不是最大骑士数所必需的）。

但这不是那么有效：您不执行对称性破坏，因此会产生很多重复项：

?- generateSolution([],4,R),length(R,4).
R = [ (1, 4), (1, 3), (1, 2), (1, 1)] ; <- duplicate of
R = [ (2, 2), (1, 3), (1, 2), (1, 1)] ;
R = [ (4, 1), (1, 3), (1, 2), (1, 1)] ;
R = [ (4, 2), (1, 3), (1, 2), (1, 1)] ;
R = [ (4, 3), (1, 3), (1, 2), (1, 1)] ;
R = [ (4, 4), (1, 3), (1, 2), (1, 1)] ;
R = [ (1, 3), (1, 4), (1, 2), (1, 1)] ; <- this one
R = [ (2, 1), (1, 4), (1, 2), (1, 1)] ;
R = [ (3, 4), (1, 4), (1, 2), (1, 1)] ;
R = [ (4, 1), (1, 4), (1, 2), (1, 1)] ;
R = [ (4, 2), (1, 4), (1, 2), (1, 1)] ;
R = [ (4, 3), (1, 4), (1, 2), (1, 1)] ;
R = [ (4, 4), (1, 4), (1, 2), (1, 1)] ;
R = [ (1, 4), (2, 1), (1, 2), (1, 1)] ;
R = [ (2, 2), (2, 1), (1, 2), (1, 1)] ;
R = [ (3, 4), (2, 1), (1, 2), (1, 1)] ;

您可以通过强制执行表明您只能增加 (X,Y) 坐标的约束来改进这一点：

% Any solution is a solution.
generateSolution(R,_,R).
% If no knight is placed on the board, select one with arbitrary `X` and `Y`.
generateSolution([],N,R) :-
    for(X,1,N),
    for(Y,1,N),
    generateSolution([(X,Y)],N,R).
% If already placed one, fetch that solution, and propose a position (X,Y) with the same X and larger Y
generateSolution([(XL,YL)|T],N,R) :-
    YL1 is YL+1,
    for(Y,YL1,N),
    \+ is_attacked(XL,Y,[(XL,YL)|T]),
    generateSolution([(XL,Y),(XL,YL)|T],N,R).
% Or generate one with a larger X
generateSolution([(XL,YL)|T],N,R) :-
    XL1 is XL+1,
    for(X,XL1,N),
    for(Y,1,N),
    \+ is_attacked(X,Y,[(XL,YL)|T]),
    generateSolution([(X,Y),(XL,YL)|T],N,R).

这里，要么Y一定比前面的Y大，要么X一定大。因此查询不再考虑重复项：

?- generateSolution([],4,R),length(R,4).
R = [ (1, 4), (1, 3), (1, 2), (1, 1)] ;
R = [ (2, 1), (1, 3), (1, 2), (1, 1)] ;
R = [ (2, 2), (1, 3), (1, 2), (1, 1)] ;
R = [ (3, 4), (1, 3), (1, 2), (1, 1)] ;
R = [ (4, 1), (1, 3), (1, 2), (1, 1)] ;
R = [ (4, 2), (1, 3), (1, 2), (1, 1)] ;
R = [ (4, 3), (1, 3), (1, 2), (1, 1)] ;
R = [ (4, 4), (1, 3), (1, 2), (1, 1)] ;
R = [ (2, 1), (1, 4), (1, 2), (1, 1)] ;
R = [ (2, 2), (1, 4), (1, 2), (1, 1)] ;
R = [ (3, 4), (1, 4), (1, 2), (1, 1)] ;
R = [ (4, 1), (1, 4), (1, 2), (1, 1)] ;
R = [ (4, 2), (1, 4), (1, 2), (1, 1)] ;
R = [ (4, 3), (1, 4), (1, 2), (1, 1)] ;
R = [ (4, 4), (1, 4), (1, 2), (1, 1)] ;
R = [ (2, 2), (2, 1), (1, 2), (1, 1)] ;
R = [ (3, 4), (2, 1), (1, 2), (1, 1)] ;
R = [ (4, 1), (2, 1), (1, 2), (1, 1)] ;
R = [ (4, 2), (2, 1), (1, 2), (1, 1)] ;
R = [ (4, 3), (2, 1), (1, 2), (1, 1)] ;
R = [ (4, 4), (2, 1), (1, 2), (1, 1)] ;
R = [ (3, 4), (2, 2), (1, 2), (1, 1)] ;
R = [ (4, 1), (2, 2), (1, 2), (1, 1)] ;

现在为了求最大骑士数，可以bootstrap:

bootstrap(N,Sol) :-
    once(bootstrap(N,[],0,Sol)).

bootstrap(N,_,I,S) :-
    once((generateSolution([],N,R),length(R,K),K > I)),
    !,
    bootstrap(N,R,K,S).
bootstrap(_,S,_,S).

谓词的工作原理如下：作为第一个解决方案，您使用 []（总是成功的空列表）。接下来开始搜索骑士多的配置：

once((generateSolution([],N,R),length(R,K),K > I)),

一旦找到这样的解决方案R，骑士数量K，你将新的解决方案作为当前解决方案，设置骑士数量并开始搜索拥有更多骑士的解决方案。如果最终失败，您 return 最后一个当前解决方案。

示例:

?- bootstrap(1,S),write(S).
[ (1,1)]
S = [ (1, 1)].

?- bootstrap(2,S),write(S).
[ (2,2), (2,1), (1,2), (1,1)]
S = [ (2, 2), (2, 1), (1, 2), (1, 1)].

?- bootstrap(3,S),write(S).
[ (3,3), (3,1), (2,2), (1,3), (1,1)]
S = [ (3, 3), (3, 1), (2, 2), (1, 3), (1, 1)].

?- bootstrap(4,S),write(S).
[ (4,4), (4,3), (4,2), (4,1), (1,4), (1,3), (1,2), (1,1)]
S = [ (4, 4), (4, 3), (4, 2), (4, 1), (1, 4), (1, 3), (1, 2), (1, 1)].

?- bootstrap(5,S),write(S).
[ (5,5), (5,3), (5,1), (4,4), (4,2), (3,5), (3,3), (3,1), (2,4), (2,2), (1,5), (1,3), (1,1)]
S = [ (5, 5), (5, 3), (5, 1), (4, 4), (4, 2), (3, 5), (3, 3), (3, 1), (..., ...)|...].

?- bootstrap(6,S),write(S).

完整代码：

bootstrap(N,Sol) :-
    once(bootstrap(N,[],0,Sol)).

bootstrap(N,_,I,S) :-
    once((generateSolution([],N,R),length(R,K),K > I)),
    !,
    bootstrap(N,R,K,S).
bootstrap(_,S,_,S).

generateSolution(R,_,R).
generateSolution([],N,R) :-
    for(X,1,N),
    for(Y,1,N),
    generateSolution([(X,Y)],N,R).
generateSolution([(XL,YL)|T],N,R) :-
    YL1 is YL+1,
    for(Y,YL1,N),
    \+ is_attacked(XL,Y,[(XL,YL)|T]),
    generateSolution([(XL,Y),(XL,YL)|T],N,R).
generateSolution([(XL,YL)|T],N,R) :-
    XL1 is XL+1,
    for(X,XL1,N),
    for(Y,1,N),
    \+ is_attacked(X,Y,[(XL,YL)|T]),
    generateSolution([(X,Y),(XL,YL)|T],N,R).

is_attacked(X,Y,PlacedKnights) :-
    member((NX,NY),PlacedKnights),
    is_attacked(X,Y,NX,NY).

is_attacked(XA,YA,XB,YB) :-
    DX is abs(XA-XB),
    DY is abs(YA-YB),
    is_attacked(DX,DY).

is_attacked(1,2).
is_attacked(2,1).

请注意，存在更聪明的技术，例如浪费大量时间来验证骑士是否受到攻击，还有其他对称性破坏方法以及防止return使用较少数量的解决方案的方法generateSolution 的骑士。这只是草图。

非回溯最优解

如您所见，几乎所有结果都遵循一种模式：

1:
+-+
|x|
+-+
2:
+-+-+
|x|x|
+-+-+
|x|x|
+-+-+
3:
+-+-+-+
|x| |x|
+-+-+-+
| |x| |
+-+-+-+
|x| |x|
+-+-+-+
4:
+-+-+-+-+
|x| |x| |
+-+-+-+-+
| |x| |x|
+-+-+-+-+
|x| |x| |
+-+-+-+-+
| |x| |x|
+-+-+-+-+

从 N 大于或等于 N 的那一刻开始出现的模式是，你在 (0,0) 上放置一个马，并且每个 (i,i+2*j) 有 i 和 j 整数（j 可以小于 0）。这是保证的最大值。

因此您可以通过以下方式生成：

solution(1,[(1,1)]).
solution(2,[(2,2),(2,1),(1,2),(1,1)]).
solution(N,L) :-
    N > 2,
    solution([],N,1,1,L).

solution(L,N,I,_,L) :-
    I > N,
    !.
solution(L,N,I,J,S) :-
    JN is J+2,
    JN =< N,
    !,
    solution([(I,J)|L],N,I,JN,S).
solution(L,N,I,J,S) :-
    IN is I+1,
    JN is (I mod 2)+1,
    IN =< N,
    !,
    solution([(I,J)|L],N,IN,JN,S).
solution(L,N,I,J,[(I,J)|L]).

示例：

?- solution(20,L),write(L).
[ (20,20), (20,18), (20,16), (20,14), (20,12), (20,10), (20,8), (20,6), (20,4), (20,2), (19,19), (19,17), (19,15), (19,13), (19,11), (19,9), (19,7), (19,5), (19,3), (19,1), (18,20), (18,18), (18,16), (18,14), (18,12), (18,10), (18,8), (18,6), (18,4), (18,2), (17,19), (17,17), (17,15), (17,13), (17,11), (17,9), (17,7), (17,5), (17,3), (17,1), (16,20), (16,18), (16,16), (16,14), (16,12), (16,10), (16,8), (16,6), (16,4), (16,2), (15,19), (15,17), (15,15), (15,13), (15,11), (15,9), (15,7), (15,5), (15,3), (15,1), (14,20), (14,18), (14,16), (14,14), (14,12), (14,10), (14,8), (14,6), (14,4), (14,2), (13,19), (13,17), (13,15), (13,13), (13,11), (13,9), (13,7), (13,5), (13,3), (13,1), (12,20), (12,18), (12,16), (12,14), (12,12), (12,10), (12,8), (12,6), (12,4), (12,2), (11,19), (11,17), (11,15), (11,13), (11,11), (11,9), (11,7), (11,5), (11,3), (11,1), (10,20), (10,18), (10,16), (10,14), (10,12), (10,10), (10,8), (10,6), (10,4), (10,2), (9,19), (9,17), (9,15), (9,13), (9,11), (9,9), (9,7), (9,5), (9,3), (9,1), (8,20), (8,18), (8,16), (8,14), (8,12), (8,10), (8,8), (8,6), (8,4), (8,2), (7,19), (7,17), (7,15), (7,13), (7,11), (7,9), (7,7), (7,5), (7,3), (7,1), (6,20), (6,18), (6,16), (6,14), (6,12), (6,10), (6,8), (6,6), (6,4), (6,2), (5,19), (5,17), (5,15), (5,13), (5,11), (5,9), (5,7), (5,5), (5,3), (5,1), (4,20), (4,18), (4,16), (4,14), (4,12), (4,10), (4,8), (4,6), (4,4), (4,2), (3,19), (3,17), (3,15), (3,13), (3,11), (3,9), (3,7), (3,5), (3,3), (3,1), (2,20), (2,18), (2,16), (2,14), (2,12), (2,10), (2,8), (2,6), (2,4), (2,2), (1,19), (1,17), (1,15), (1,13), (1,11), (1,9), (1,7), (1,5), (1,3), (1,1)]
L = [ (20, 20), (20, 18), (20, 16), (20, 14), (20, 12), (20, 10), (20, 8), (20, 6), (..., ...)|...].

或图形表示：

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Prolog：不断得到错误的结果

Prolog : Keep getting false result

prolog