元皇后问题回溯算法改进  

Solving N-queens problem by using improved backtracking algorithm

作　　者：钱卫[1] 张钟澍[1] 张奎良[1] 

机构地区：[1]成都信息工程学院计算机系,成都610225

出　　处：《四川大学学报（自然科学版）》2009年第2期339-342,共4页Journal of Sichuan University(Natural Science Edition)

基　　金：四川省教育厅自然科学重点项目(072A014)

摘　　要：回溯算法是解决N元皇后问题最有效的算法之一。在传统回溯算法的基础上,采用动态规划的思想,对算法进行了改进,改进后的算法大大降低了求解的复杂度和比较次数。文章还给出了改进算法的实现并通过理论分析和实验数据证明了算法的可行性。Backtracking algorithm is one of the efficient methods to solve N-queens problem. Based on the solving N-queens problem by using backtracking algorithm, the thinking of the dynamic programming was introduced to improve the algorithm, and the complexity of the solution and comparative number was greatly reduced. At the same time, the concrete realization of the improved Non-recursive algorithm was implemented and the feasibility of this algorithm was proved through theoretical analysis and experimental data in the paper.

关 键 词：回溯算法 皇后问题 动态规划 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]