2

我正在为大学考试学习 Prolog，但我对以下练习有一些问题。

我有以下 8 皇后问题的经典解决方案（这对我来说不是问题），修改这个解决方案我必须为处理可变数量皇后的更通用的 n 皇后问题创建一个新的解决方案。

solution([]).

solution([X/Y|Others]) :- solution(Others),
                          member(Y,[1,2,3,4,5,6,7,8]),
                          noattack(X/Y, Others).

noattack(_,[]).

noattack(X/Y, [X1/Y1 | Others]) :-
                      Y =\= Y1,       % Q e Q1 sono su righe diverse
                      % Q e Q1 sono su diagonali diverse:
                      Y1-Y =\= X1-X,
                      Y1-Y =\= X-X1,
                      % Q non attacca regine nella sottolista Others:
                      noattack( X/Y, Others).

% TEMPLATE DELLE SOLUZIONI: c'è una regina su ogni colonna:
template([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).

好的，这个程序看起来很简单：我有一个女王列表，他们不能互相攻击。

如果女王列表为空，则女王不可能攻击列表中的另一个女王，因此空列表是问题的解决方案（它是解决方案的基本情况）

*如果皇后列表不为空，我可以将其划分为 [X/Y|Others] 其中 X/Y 在列表中第一个皇后的棋盘上的位置* （位置是夫妇的 rappresentend (X,Y ) 其中 X 是列，Y 是行)

因此，如果以下关系为真，则列表 [X/Y|Others] 是问题的解决方案是真的：

  1. 子列表 Others 本身就是一个解决方案（Others 不包含攻击列表中其他女王的女王）

  2. Y 属于 1 到 8 之间的整数值（因为我有 8 行）

  3. 列表的第一个女王不要攻击子列表中的其他女王

然后定义了noattack关系，它指定我什么时候可以说一个女王不攻击另一个女王是真的（这很简单：他们不能停留在同一行，同一列，同一对角线）

最后，我有一个解决方案模板，可以简化我的生活，将 X 值限制在 1 到 8 之间（因为我知道 2 个皇后不能留在同一列……所以解决方案中的每个皇后都留在不同的列所有其他皇后）

所以我认为最大的问题在于我指定列数的那一行：

member(Y,[1,2,3,4,5,6,7,8])

在我定义解决方案模板的那一行：

template([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).

我不知道如何扩展以前的解决方案来处理可变数量的皇后。

4

1 回答 1

2

似乎很容易，传递大小：

solution(_, []).
solution(N, [X/Y|Others]) :-
    solution(N, Others),
    between(1, N, Y),
    noattack(X/Y, Others).

noattack(_,[]).
noattack(X/Y, [X1/Y1 | Others]) :-
    Y =\= Y1,       % Q e Q1 sono su righe diverse
    Y1-Y =\= X1-X,  % Q e Q1 sono su diagonali diverse
    Y1-Y =\= X-X1,
    noattack( X/Y, Others). % Q non attacca regine nella sottolista Others

% TEMPLATE DELLE SOLUZIONI: c'è una regina su ogni colonna:
template(N, L) :-
    findall(I/_, between(1,N,I), L).

测试：

?- N=6, template(N, L), solution(N, L).
N = 6,
L = [1/5, 2/3, 3/1, 4/6, 5/4, 6/2] ;
N = 6,
L = [1/4, 2/1, 3/5, 4/2, 5/6, 6/3] ;
N = 6,
L = [1/3, 2/6, 3/2, 4/5, 5/1, 6/4] ;
N = 6,
L = [1/2, 2/4, 3/6, 4/1, 5/3, 6/5] ;
false.

（我应该画出来说好不好……）

于 2013-04-05T19:42:11.587 回答