在人工智能与逻辑编程的教学中，N皇后问题常被用作经典案例——如何在N×N的棋盘上放置N个皇后，使其互不攻击。多数Prolog教程倾向于使用CLPFD（约束逻辑编程于有限域）库，通过声明式约束高效求解。然而，在某些教学环境或旧版系统中，CLPFD可能不可用，或学习者希望深入理解朴素回溯算法的实现。本文将为读者详细演示如何仅用SWI-Prolog内置谓词，不借助任何外部库，完成N皇后问题的求解。

问题描述与解题思路

N皇后问题的核心是：任意两个皇后不能在同一行、同一列或同一对角线上。在Prolog中，我们不显式维护棋盘矩阵，而是用列表表示每行皇后所在的列位置。例如，列表[3,1,6,2,5,7,4]表示一个6×6棋盘上，第1行皇后在第3列，第2行在第1列，以此类推。通过“行号隐式对应列表索引”，我们只需确保列号互不重复，且对角线差值的绝对值不等于行号差。

典型的回溯搜索策略是“生成-测试”（generate and test）。先用permutation/2或select/3生成所有可能的列排列，再用安全谓词safe/1筛选出合法放置。但全排列生成在N较大时效率极低，更实用的做法是“一边放置一边剪枝”，即通过递归逐步构造皇后列表，并在每一步检查新放置的皇后是否与已有皇后冲突。

核心谓词实现

我们定义主谓词n_queens(N, Queens)，返回解列表。以下为完整代码（不使用CLPFD）：

n_queens(N, Queens) :-
    length(Queens, N),          % 预分配N个位置的列表
    place_queens(Queens, [], _). % 辅助谓词

place_queens/3的语义：第一个参数是待填充的皇后列表（初始为自由变量），第二个参数是已放置的皇后列表（逆序），第三个参数是当前行号（从1开始）。递归基本情形：当待填充列表为空时，所有皇后已成功放置。

place_queens([], _, _).
place_queens([Col|Rest], Placed, Row) :-
    between(1, N, Col),          % 枚举列号1至N
    no_attack(Col, Row, Placed), % 检查新皇后与已放置皇后是否冲突
    NextRow is Row + 1,
    place_queens(Rest, [Col|Placed], NextRow).

其中no_attack/3需要判断新皇后（在行Row、列Col）与已放置皇后（列表Placed，每个元素为列号，所在行号由索引决定）是否满足列不同、对角线差不等：

no_attack(_, _, []). % 空列表自然安全
no_attack(Col, Row, [PlacedCol|PlacedRest]) :-
    Col \= PlacedCol,                              % 不同列
    RowDiff is Row - length(PlacedRest) - 1,       % 已放置皇后所在行号（从1开始）
    abs(Col - PlacedCol) =\= RowDiff,              % 对角线安全
    no_attack(Col, Row, PlacedRest).

注意：这里计算已放置皇后的行号时，利用PlacedRest的长度——因为Placed列表是逆序存放（最新皇后在头部），所以从头部到当前元素的索引差可以反映行号。更简单的实现是让place_queens同时携带当前行号，已放置队列正向存储，但上述写法保持了Prolog典型风格。

调用与示例

编译代码后，查询n_queens(4, Q).会依次返回所有解：

Q = [2, 4, 1, 3] ;
Q = [3, 1, 4, 2] ;

若只求第一个解，可以用once/1。对于N=8，典型单解求解时间在几十毫秒内（取决于具体硬件），而求全部解则需数秒，这比使用CLPFD的label/1方法慢约一个数量级，但已能应对N≤12的教学场景。

性能讨论与优化方向

朴素回溯的弱点在于：每次between/3生成的列号可能被后续大量无效尝试浪费。可引入“列号候选列表”来减少枚举，例如使用select/3从剩余列中依次选取，这样能自动保证列不重复：

place_queens(_, [], _).
place_queens(Candidates, [Col|Rest], Row) :-
    select(Col, Candidates, NewCandidates),
    no_attack_diag(Col, Row, Rest, 1), % 需修改对角检查
    NextRow is Row + 1,
    place_queens(NewCandidates, Rest, NextRow).

这种方法将列去重内化，减少了no_attack中列判断的开销，但对于大N仍面临组合爆炸。更高效的“前向检查”或“智能回溯”实现则需更多编程技巧。

与其他方法的对比

使用CLPFD的典型解法为：

:- use_module(library(clpfd)).

n_queens_clpfd(N, Q) :-
    length(Q, N),
    Q ins 1..N,
    all_different(Q),
    all_different([Q[I] - I | I in 1..N]),
    all_different([Q[I] + I | I in 1..N]),
    label(Q).

CLPFD的声明式约束加上高效的域传播算法，使其在N=20时仍能迅速求解，而非CLPFD版在N=15时已难以承受。这正体现了约束编程在组合优化问题上的核心优势——用较少的代码换取巨大的性能提升。

结语

尽管不使用CLPFD的解决方案在性能上无法与之匹敌，但作为理解Prolog回溯机制、递归列表操作和冲突检查逻辑的练习，它依然具有很高的教学价值。当你在受限环境（如在线判题系统）或追求纯粹逻辑编程体验时，掌握这种“手写”解法能让你更透彻地洞察Prolog的工作原理。未来，如果遇到类似问题，不妨先尝试用纯Prolog实现，再与CLPFD版本对比，感受声明式编程的演进之美。