软件工程

本类阅读TOP10

·PHP4 + MYSQL + APACHE 在 WIN 系统下的安装、配置
·Linux 入门常用命令(1)
·Linux 入门常用命令(2)
·使用 DCPROMO/FORCEREMOVAL 命令强制将 Active Directory 域控制器降级
·DirectShow学习(八): CBaseRender类及相应Pin类的源代码分析
·基于ICE方式SIP信令穿透Symmetric NAT技术研究
·Windows 2003网络负载均衡的实现
·一网打尽Win十四种系统故障解决方法
·数百种 Windows 软件的免费替代品列表
·收藏---行百里半九十

分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
The BackTracking algorithm for n queen problem

作者:未知 来源:月光软件站 加入时间:2005-5-13 月光软件站

The article is about the design of algorithm for n queen problem. The intention of this article is from an excise of an algorithm book: <<Introduction to the design and analysis of algorithms>>. This backtracking algorithm is interesting, so I decide to record the process of implementation. First, I use a double dimension array to simulate the chess board. But quickly I have found this form of representation is not so convenient especially in the check function that is used to checking whether or not current solution is promising. Because the check function is worked with the index of array, the value of array is trivial. i.e. a[0][0] = 1 represent (0,0) position of chess board has a chess and the next chess can't be position (0,1) and (0,0). So I have changed a representation of chess position by vector<pair<int,int> >. Apparently, pair<int, int> stands for (x,y). Notice that a solution of n queen require each row is different. That is, for a solution of n queen, each of pair_instance.first must distinct. This simplifies the representation further. It just needs a vector<int> to represent a chess board. So the solution of n queen problem can be viewed as a permutation of natural number from 0 to n-1. Apparently, the brute-force algorithm has efficiency


相关文章

相关软件