Prolog编程
我使用爬山和光束搜索算法在Prolog中为nqueens拼图制作了两个程序。
不幸的是，我没有经验来检查程序是否正确并且我处于死胡同。
如果有人可以帮助我，我将不胜感激。
不幸的是，登山计划不正确。
:(
queens(N, Qs) :-
range(1, N, Ns),
queens(Ns, [], Qs).
range(N, N, [N]) :- !.
range(M, N, [M|Ns]) :-
M < N,
M1 is M+1,
range(M1, N, Ns).
queens([], Qs, Qs).
queens(UnplacedQs, SafeQs, Qs) :-
select(UnplacedQs, UnplacedQs1,Q),
not_attack(SafeQs, Q),
queens(UnplacedQs1, [Q|SafeQs], Qs).
not_attack(Xs, X) :-
not_attack(Xs, X, 1).
not_attack([], _, _) :- !.
not_attack([Y|Ys], X, N) :-
X == Y+N,
X == Y-N,
N1 is N+1,
not_attack(Ys, X, N1).
select([X|Xs], Xs, X).
select([Y|Ys], [Y|Zs], X) :- select(Ys, Zs, X).
没有找到相关结果
已邀请:
3 个回复
搜洼挂时
:- use_module(library(clpfd)). queens(N, L) :- N #> 0, length(L, N), L ins 1..N, all_different(L), applyConstraintOnDescDiag(L), applyConstraintOnAscDiag(L), label(L). applyConstraintOnDescDiag([]) :- !. applyConstraintOnDescDiag([H|T]) :- insertConstraintOnDescDiag(H, T, 1), applyConstraintOnDescDiag(T). insertConstraintOnDescDiag(_, [], _) :- !. insertConstraintOnDescDiag(X, [H|T], N) :- H #= X + N, M is N + 1, insertConstraintOnDescDiag(X, T, M). applyConstraintOnAscDiag([]) :- !. applyConstraintOnAscDiag([H|T]) :- insertConstraintOnAscDiag(H, T, 1), applyConstraintOnAscDiag(T). insertConstraintOnAscDiag(_, [], _) :- !. insertConstraintOnAscDiag(X, [H|T], N) :- H #= X - N, M is N + 1, insertConstraintOnAscDiag(X, T, M).是女王的数量或者棋盘的大小（），其中，是女王在线上的位置。 让我们详细介绍上面算法的每个部分，以了解会发生什么。它向SWI-Prolog指示加载包含约束满足问题的谓词的模块。queens(N, L) :- N #> 0, length(L, N), L ins 1..N, all_different(L), applyConstraintOnDescDiag(L), applyConstraintOnAscDiag(L), label(L).谓词是算法的入口点，并检查术语是否格式正确（数字范围，列表长度）。它会检查女王是否在不同的线路上。applyConstraintOnDescDiag([]) :- !. applyConstraintOnDescDiag([H|T]) :- insertConstraintOnDescDiag(H, T, 1), applyConstraintOnDescDiag(T). insertConstraintOnDescDiag(_, [], _) :- !. insertConstraintOnDescDiag(X, [H|T], N) :- H #= X + N, M is N + 1, insertConstraintOnDescDiag(X, T, M).applyConstraintOnAscDiag([]) :- !. applyConstraintOnAscDiag([H|T]) :- insertConstraintOnAscDiag(H, T, 1), applyConstraintOnAscDiag(T). insertConstraintOnAscDiag(_, [], _) :- !. insertConstraintOnAscDiag(X, [H|T], N) :- H #= X - N, M is N + 1, insertConstraintOnAscDiag(X, T, M).可以找到结果，例如：舜辉
queens(0, []). queens(N, [Q|Qs]) :- M is N-1, queens(M, Qs), between(1, N, Q), safe(Q, Qs).攻击，则为真。是一个简单的检查（参见SWI-Prolog手册）和你的谓词的结合，乍一看似乎是正确的。熊融炭臀陛
% This program finds a solution to the 8 queens problem. That is, the problem of placing 8 % queens on an 8x8 chessboard so that no two queens attack each other. The prototype % board is passed in as a list with the rows instantiated from 1 to 8, and a corresponding % variable for each column. The Prolog program instantiates those column variables as it % finds the solution. % Programmed by Ron Danielson, from an idea by Ivan Bratko. % 2/17/00 queens([]). % when place queen in empty list, solution found queens([ Row/Col | Rest]) :- % otherwise, for each row queens(Rest), % place a queen in each higher numbered row member(Col, [1,2,3,4,5,6,7,8]), % pick one of the possible column positions safe( Row/Col, Rest). % and see if that is a safe position % if not, fail back and try another column, until % the columns are all tried, when fail back to % previous row safe(Anything, []). % the empty board is always safe safe(Row/Col, [Row1/Col1 | Rest]) :- % see if attack the queen in next row down Col == Col1, % same column? Col1 - Col == Row1 - Row, % check diagonal Col1 - Col == Row - Row1, safe(Row/Col, Rest). % no attack on next row, try the rest of board member(X, [X | Tail]). % member will pick successive column values member(X, [Head | Tail]) :- member(X, Tail). board([1/C1, 2/C2, 3/C3, 4/C4, 5/C5, 6/C6, 7/C7, 8/C8]). % prototype board