# 用Prolog和Erlang解决N queens问题

```queens(N,Qs):-
range(1,N,Ns),
queens(Ns,[],Qs).

queens([],Qs,Qs).
queens(UnplacedQs,SafeQs,Qs):-
sel(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).

sel([X|Xs],Xs,X).
sel([Y|Ys],[Y|Zs],X):-
sel(Ys,Zs,X).

range(N,N,[N]):- !.
range(M,N,[M|Ns]):-
M < N,
M1 is M+1,
range(M1,N,Ns).```

看看运行结果：

```[root@localhost Prolog]# gplc queen.pl
[root@localhost Prolog]# ./queen
GNU Prolog 1.3.1
By Daniel Diaz
| ?- queens(8, Q).

Q = [4,2,7,3,6,8,5,1] ? ;

Q = [5,2,4,7,3,8,6,1] ? ;

Q = [3,5,2,8,6,4,7,1] ? ;

Q = [3,6,4,2,8,5,7,1] ? ;

Q = [5,7,1,3,8,6,4,2] ? ;

Q = [4,6,8,3,1,7,5,2] ? ;

Q = [3,6,8,1,4,7,5,2] ? ;

Q = [5,3,8,4,7,1,6,2] ? ;

Q = [5,7,4,1,3,8,6,2] ? ;

Q = [4,1,5,8,6,3,7,2] ? ;

Q = [3,6,4,1,8,5,7,2] ? ;

Q = [4,7,5,3,1,6,8,2] ? ;

Q = [6,4,2,8,5,7,1,3] ? ```

Prolog语法与Erlang很像，Erlang可是Joe在Prolog的语法基础上加了concurrent，Joe声称他当时是很喜欢Prolog的。

```-module(queens).
-export([queens/1]).

perms([]) -> [[]];
perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].

noattack([]) -> true;
noattack([H|L]) -> noattack(L, H, 1) and noattack(L).
noattack([H|L], X, N) -> (X =/= H+N) and (X =/= H-N) and noattack(L, X, N+1);
noattack([], _, _) -> true.

queens(L) -> [E || E <- perms(L), noattack(E) =:= true].```

总共7行Erlang代码就可解决N queens问题，里面都是递归，List comprehensions也是compiler编译成递归程序的，上面7行代码还可以再减少吗？好吧，再来减少一行：

```-export([queens/1]).

perms([]) -> [[]];
perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].

noattack([H|L]) -> noattack(L, H, 1).
noattack([H|L], X, N) -> (X =/= H+N) and (X =/= H-N) and noattack(L, X, N+1) and noattack(L, H, 1);
noattack([], _, _) -> true.

queens(L) -> [E || E <- perms(L), noattack(E) =:= true].```

与上面那个程序不同，很多递归不是尾递归，所以虽然代码行数少了一行，但没有第一个程序效率好。

结论：List comprehensions对于解决很多Logic问题是多么的方便啊！

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two