软件工程

本类阅读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开发
Space and time trade-off in n queen problem

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

The backtracking algorithm of n queen problem can be improved by space and time trade-off further. The consideration of positions occupancy is attained by duplicate_array and two integrals. Note that these utilities can’t tell all illegal moves because it is performing its job on the basis of chess_board definition. That is, power of utilities contained by chess_board are not enough to telling all illegal moves. It needs a data structure to record positions occupied by chesses. Naturally, it needs three arrays to recording row, column, diagonal1 (upper left to lower right) and diagonal2 (upper right to lower left). Column is already represented by duplicate_array. So it needs two other array to represent diagonal1,2. Consequently, the job is how to express the meaning of one diagonal is occupied. That is, for a move: (cur_i, j), how to assign value to the corresponding element in diagonal1,2. Assuming the one of occupied diagonal1 is diagonal1[x] and diagonal2 is diagonal2[y], then assign diagonal1[x] and diagonal2[y] to 1 to denoting these diagonals are occupied. An n queen problem has 2n-1 diagonal1s and 2n-1 diagonal2s. The rules are:


相关文章

相关软件