一本通-1213：八皇后问题（回溯+搜索）

【题目描述】 在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。

【输入】 (无)

【输出】 按给定顺序和格式输出所有八皇后问题的解（见样例）。

【输入样例】 (无)

【输出样例】

No. 1 1 0 0 0 0 0 0 0  0 0 0 0 0 0 1 0  0 0 0 0 1 0 0 0  0 0 0 0 0 0 0 1  0 1 0 0 0 0 0 0  0 0 0 1 0 0 0 0  0 0 0 0 0 1 0 0  0 0 1 0 0 0 0 0  No. 2 1 0 0 0 0 0 0 0  0 0 0 0 0 0 1 0  0 0 0 1 0 0 0 0  0 0 0 0 0 1 0 0  0 0 0 0 0 0 0 1  0 1 0 0 0 0 0 0  0 0 0 0 1 0 0 0  0 0 1 0 0 0 0 0  ...以下省略

---

这道题目限定了输出的格式，会发现和正常的输出还是有一点差距的，借用博客里的一张图：

发现其实搜索思路仍然不变，只是在输出的时候，将预先设定的行和列进行了交换。

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

int n;
vector<int> res(8, -1);
int cnt = 0;
vector<vector<int> > grid(8, vector<int>(8));

bool canPlace(int row, int col)
{
    for (int i = 0; i < row; ++i) {
        if (res[i] == col || abs(row - i) == abs(res[i] - col))
            return false;
    }

    return true;
}

void DFS(int row, int n)
{
    for (int col = 0; col < n; ++col) {
        if (canPlace(row, col)) {
            res[row] = col;
            if (row == n - 1) {
                ++cnt; //找到一种解决方案
                cout << "No. " << cnt << endl;
                for (int i = 0; i < 8; ++i) grid[res[i]][i] = 1;
                for (int i = 0; i < 8; ++i) {
                    for (int j = 0; j < 8; ++j) {
                        cout << grid[i][j];
                        if (j != n - 1) cout << ' ';
                    }
                    cout << endl;
                }

                for (int i = 0; i < 8; ++i)
                    fill(grid[i].begin(), grid[i].end(), 0);
            }
            else DFS(row + 1, n);
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    DFS(0, 8);

    return 0;
}