用Prolog和Erlang解决N queens问题
对于这种queens解法，Prolog语言可谓得心应手，Prolog本身发明就是为了解决这种逻辑问题，其中运用了大量了递归。
?
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.1By Daniel DiazCopyright (C) 1999-2009 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的。
?
? 既然Erlang和Prolog语法很相似，那么看看用Erlang写个N queens是什么样子？其实很多逻辑问题用FP中的List comprehensions可以很好的表达（Python，Erlang，Haskell都有这功能），而且基本上可以模拟简单的Prolog逻辑了（测试中竟发现下面的perm函数如果写在escript中竟不起作用，奇怪？escript不能支持List comprehensions？），下面就用用这个List comprehensions吧：
?
-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].
?与上面那个程序不同，很多递归不是尾递归，所以虽然代码行数少了一行，但没有第一个程序效率好。
?
? ?由于Erlang shell中不能解释函数（Haskell shell中也不行），所以N queens问题无法用一行搞定，有时间看看python能否用一行搞定这个问题。
?
? ?结论：List comprehensions对于解决很多Logic问题是多么的方便啊！
