百练-2754-八皇后-解题报告

---

描述
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。
给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 <= b <= 92)

输出
输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。

样例输入
2
1
92

样例输出
15863724
84136275

---

代码：

#include <iostream>
#include <cmath>

using namespace std;

const int QUEENS  = 8;

/*用来存放一种摆放方法，下标的范围从1->QUEENS。
 *下标i表示第i个皇后，同时也表时第i个皇后处于第i行；
 *cols[i]则表示该皇后处于第cols[i]列。
 */
int cols[QUEENS + 1];

/*核心函数，递归求得所有的摆事实放方法。*/
void putQueens(int n);
/*输出函数*/
void output();
/*检测函数，对第n个皇后的位置是否合法进行检测*/
bool isValid(int n);

void putQueens(int n) {
    /*若前面QUEENS个皇后已经摆放好，则输出并返回*/
    if(n > QUEENS) {
        output();
        return ;
    }

    /*否则，对第n个皇后的列的所有可能位置进行试探*/
    for(int i = 1; i <= QUEENS; i++) {
        cols[n] = i;

        /*若该位置合法，则进行下一个皇后的摆放。
         *否则，再进入下一个列的位置的检测。（i++）
         */
        if(isValid(n)) {
            putQueens(n + 1);
        }
    }
}

bool isValid(int n) {
    /*第n个皇后的列的位置为cols[n]。
     *要检测当前第n个皇后的位置是否合法，则要与前面n-1个皇后检查。
     *以下两个条件不合法：
     *（1）两个皇后处于同一列：cols[i] == cols[n] ？
     *（2）两个皇后处于对角线：fabs(cols[i] - cols[n]) == n - i ？其中n-i为两个皇后的行数相减。
     *两个皇后是否处于同一行是不用判断的，因为用cols存储时已默认第n个皇后处于第n行。
     */
    for(int i = 1; i < n; i++) {
        if(cols[i] == cols[n] || fabs(cols[i] - cols[n]) == n - i)
            return false;
    }

    /*检测了与所有已摆入的皇后的位置都不冲突，返回true*/
    return true;
}

void output() {
    /*输出，记得下标从1开始即可*/
    for(int i = 1; i <= QUEENS; i++)
        cout << cols[i];
    cout << " ";
}

int main()
{
    /*调用核心函数*/
    putQueens(1);
    cout << endl;

    return 0;
}

为了更清楚说明算法，代码略去了输入。

输出结果如下：