求助：如何为Constraint Handling Rules实现N皇后问题的回溯求解

我在使用Constraint Handling Rules（CHR）解决需要回溯的N皇后问题时遇到了明显问题，相信存在相关经典解法但未能找到。我的代码如下：

:- use_module(library(chr)).

:- chr_constraint board(+int), free(+int, +int), queen/0, queen(+int, +int). 
:- chr_constraint attacked(+int, +int), queens(+int), n_queens(+int).

%% initialize the board
board(N) <=> foreach(between(1, N, X), foreach(between(1, N, Y), free(X, Y))).

%% place a queen
queen, free(X, Y) <=> queen(X, Y).
queen(X, _) \ free(X, F) <=> attacked(X, F).
queen(_, Y) \ free(F, Y) <=> attacked(F, Y).
queen(X1, Y1) \ free(X2, Y2) <=> diagonal(X1, Y1, X2, Y2) | attacked(X2, Y2).

%% generate all the necessary queens
queens(0) <=> true.
queens(N) <=> queen, succ(N0, N), queens(N0).

%% ascertain if two points are on the same diagonal
diagonal(X1, Y1, X2, Y2) :- 
    abs(X1 - X2) =:= abs(Y1 - Y2).

n_queens(N) <=> board(N), queens(N).

main :- 
    n_queens(8).

运行后生成了如下不完整的解：

queen,
queen,
queen,
queen(4, 5),
queen(5, 7),
queen(6, 4),
queen(7, 6),
queen(8, 8),
...

请问是否有直接的方法让CHR支持回溯以找到正确的N皇后问题解？

CHR本身是基于约束传播的确定性规则引擎，但可以结合Prolog的回溯机制实现N皇后问题的完整求解。核心问题是你原来的代码用了确定性简化规则（<=>）直接消耗约束，没有留下回溯选择点，导致路径走死时无法尝试其他位置。

修改后的代码 #

:- use_module(library(chr)).

:- chr_constraint board(+int), free(+int, +int), queen/0, queen(+int, +int). 
:- chr_constraint attacked(+int, +int), queens(+int), n_queens(+int).

%% 初始化棋盘
board(N) <=> foreach(between(1, N, X), foreach(between(1, N, Y), free(X, Y))).

%% 非确定性放置皇后：利用Prolog回溯尝试所有可行位置
queen ==> free(X, Y), queen(X, Y).

%% 标记被攻击的位置（约束传播规则不变）
queen(X, _) \ free(X, F) <=> attacked(X, F).
queen(_, Y) \ free(F, Y) <=> attacked(F, Y).
queen(X1, Y1) \ free(X2, Y2) <=> diagonal(X1, Y1, X2, Y2) | attacked(X2, Y2).

%% 生成N个皇后需求
queens(0) <=> true.
queens(N) <=> queen, succ(N0, N), queens(N0).

%% 判断对角线
diagonal(X1, Y1, X2, Y2) :- 
    abs(X1 - X2) =:= abs(Y1 - Y2).

%% 启动问题
n_queens(N) <=> board(N), queens(N).

%% 收集并输出所有解
main :- 
    n_queens(8),
    findall(queen(X,Y), queen(X,Y), Queens),
    writeln(Queens),
    fail. % 触发回溯寻找下一个解
main. % 结束回溯

关键修改说明 #

• 替换简化规则为传播规则：将queen, free(X, Y) <=> queen(X, Y)改为queen ==> free(X, Y), queen(X, Y)。
  • <=>是简化规则，会直接消耗queen和free(X,Y)约束，没有回溯可能；
  • ==>是传播规则，触发时会通过Prolog的free(X,Y)目标遍历所有可行位置，当当前选择导致后续无法放置皇后时，Prolog会自动回溯到该选择点，尝试下一个未被攻击的位置。
• 添加回溯触发逻辑：在main中用fail触发回溯，配合findall可以收集所有合法解，或者逐个输出。

优化建议 #

可以进一步缩小搜索空间，比如强制每个皇后放在不同的行，减少不必要的回溯：

%% 按行放置皇后，减少搜索范围
queen(Row) ==> free(Row, Col), queen(Row, Col).

%% 修改生成皇后的规则
queens(N, N) <=> true.
queens(Current, N) <=> queen(Current), succ(Current, Next), queens(Next, N).

n_queens(N) <=> board(N), queens(1, N).

这样每一行只放一个皇后，大幅提升搜索效率。

内容的提问来源于stack exchange，提问作者Daniel Lyons