N皇后问题的回溯算法改进  

Solving N-Queens Problem by Using Improved Backtracking Algorithm

作　　者：刘寒冰[1] 李福荣[2] 叶茂功[1] 

机构地区：[1]黄河科技学院,河南郑州450063 [2]黄淮学院,河南驻马店463000

出　　处：《软件导刊》2010年第7期63-65,共3页Software Guide

基　　金：河南省自然科学基金项目(092300410217)

摘　　要：回溯算法是解决N皇后问题的经典算法。在分析N皇后问题的解结构的基础上,优化了利用回溯法求解N皇后问题的解空间树,并改进了互不攻击的条件,大大地减少了比较次数和求解的复杂度,通过理论分析和实验证明了改进算法的可行性。The backtracking algorithm is the classical algorithm for solving N-queens problem. Based on the analysis about the solution structure of N-queens problem,we improve the backtracking algorithm of the N-queens problem by remodeling the solution structure tree,and improve the method which checks the N-queens not to attack each other. So the complexity of the solution and comparative number was greatly reduced. And the feasibility of the algorithm was proved through theoretical analysis and experimental data in the paper.

关 键 词：N皇后 回溯算法 解空间树 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]