n皇后问题.doc

n 皇后问题是递归和回溯法的一个典型应用。问题描述如下:对于一个 n×n 的棋盘,要求在其中放入互不攻击的 n 个皇后。皇后的攻击范围包括: 1) 同一行 2) 同一列 3) 同一对角线(包括两个方向) 分析后可见,皇后之间互不攻击当且仅当满足下列条件: 1) 每一行只能有一个皇后 2) 每一列只能有一个皇后 3) 任意条对角线上面只能有一个皇后若按照从左到右从上到下的顺序手动摆放皇后, 会发现算法遵循的是回溯法的思想。于是我们遵循 top-down design 的顺序来设计整个算法和程序。采用 OOP 的思想,先假设存在一个· 表示棋盘格局的类 queens ,则定义回溯函数 solve_from(queens configuration) , configuration 表示当前棋盘格局,算法不断扩展棋盘的当前格局(找到下一个非冲突位置) ,当找到一个解决方案时打印该方案。该递归函数采用回溯法求出所有解。 main 函数调用 solve_from 时传递的实参是一个空棋盘。对于模拟棋盘的 queens 类,我们可以定义三个数据成员: 1) size :棋盘的边长,即大小 2) count :已放置的互不冲突的皇后数 3) array[][] :布尔矩阵, true 表示当前格有皇后这里需要稍加思考以便稍后可以简化程序: 因为每行只能放一个皇后, 从上到下, 从左到右放,那么 count 个皇后占用的行为 0 —— count -1 。所以 count 还表示下一个皇后应该添加在哪一行。这样, add 和 remove 操作的入口参数就只需要提供列号就行了, 降低了耦合度:) 为了模拟棋盘操作,应该至少提供以下方法: 1) 初始化一个 size 大小的空棋盘 queens(int size) 2) 插入一个非冲突的皇后 add( int col ) 3) 删除最新插入的皇后 remove( int col ) 4) 判断要插入的皇后是否与已存在的棋盘格局相冲突 bool guarded( int col ) 5) 判断是否棋盘已满 bool finished( ) 6) 若棋盘已满则打印棋盘格局 print() 于是 solve_from 定义如下: void solve_from( queens &configuration ) { if( () ) (); else for( int i=0; i<size; i++ ) if( !( i)) { ( i ); solve_from(configuration); ( i ); }} queens 的方法实现如下: static const int MAX_SIZE = 20 queens::queens( const int & size ){ for( int i=0; i<MAX_SIZE; i++ ) for( int j=0; j<MAX_SIZE; j++ ) array[ i ][j]= false; this->size = size; count = 0; } void queen