2009-2010学年第二学期《计算机算法设计与分析》试卷A--参考答案（软07级）

2．（15分）设n后问题的显约束条件是两个皇后不能在同一行及同一列，求解n后问题的递归的回溯算法如下。它计算可行解的个数，并将所有可行解输出。请给算法填空（包括部分循环语句和条件判断语句后面的注释）。

设x[i]的初值为i（1≤i≤n），sum的初值为0。

bool Queen :: Place(int k) {for (int j=1； j

if( abs(k-j)==abs(x[j]-x[k]) ) // 判断两个皇后是否在同一斜线 return false; return true ; }

void Queen：：Backtrack(int t) {if (t>n) // 得到一个可行解 {sum++; // 可行解个数加1 for( int i=1; i<=n; i++ ) //输出可行解 count<

else for ((int j= t ； j<=n ； j++ ) {Swap（ x[t] ， x[j] ）；

if (Place(t)) // 检查第t个皇后与前t-1个皇后是否在同一斜线 Backtrack( t+1 )； Swap（ x[t] ， x[j] ） ； } }

5