当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

用Prolog和Erlang解决N queens问题

发表于: 2012-02-06   作者:bookjovi   来源:转载   浏览次数:
摘要: 对于这种queens解法,Prolog语言可谓得心应手,Prolog本身发明就是为了解决这种逻辑问题,其中运用了大量了递归。   queens(N,Qs):- range(1,N,Ns), queens(Ns,[],Qs). queens([],Qs,Qs). queens(UnplacedQs,SafeQs,Qs):-

对于这种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.1
By Daniel Diaz
Copyright (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问题是多么的方便啊!

用Prolog和Erlang解决N queens问题

  • 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
最近枕头书是《七周七语言:理解多种编程范型》这本,前面两章分别看了Ruby和IO,都是命令式语言。虽
最近枕头书是《七周七语言:理解多种编程范型》这本,前面两章分别看了Ruby和IO,都是命令式语言。虽
使用sax解析XML时,经常会遇到Content is not allowed in prolog异常,原因有两种 1、XML格式错误 2
一道常见的填字游戏题目,题目如下: 在上面的白色方框内填入适合的单词,可供选择的单词有:dog,run
一道常见的填字游戏题目,题目如下: 在上面的白色方框内填入适合的单词,可供选择的单词有:dog,run
原文 : http://blog.hesey.net/2011/09/resolve-aba-by-atomicstampedreference.html 在运用CAS做L
数据结构里面有个比较著名的八皇后问题,其解决方式倒有很多种,而搜索树又算是一个人工智能方面的
之前研究了一个问题"[Erlang 0050]用fun在Erlang Shell中编写尾递归",一直对这个问题保持着关注;最
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号