n queens ii（n皇后问题-只计数不保存）

问题描述

The n queens puzzle is the problem of placing n queens on an N x Nchessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where'Q'and'.'both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

题目大意

著名n皇后问题。
n个皇后摆放在N x N的棋盘格中，使得横、竖和两个对角线方向均不会同时出现两个皇后。

解题思路

n皇后问题当n大于等于4才有讨论意义，而且不只有一个解决方案；
用递归的方法找到每一种解决方案；
在当前解决方案中，遍历每一行的每一列查找可以放置皇后的位置；
在当前行中，遍历每一列的每一个位置，假设当前位置可以放，然后进行合法性判断，合法则放置；
然后再递归判断下一行；
递归结束后，将当前行当前列的位置回溯，置为未放状态，再接着判断当前行下一列，目的是为了找到所有的解决方案。

代码

#include<iostream>
#include<vector>
using namespace std;

/*
    函数声明
*/
// 解决方案函数
vector<vector<string > > solveNQueens(int n);
// 用深度优先搜索的递归实现进行查找解决方案
void dfs(vector<vector<string > > &res, vector<string > &cur, int &n, int row);
// 判断是否可以在当前的row行col列进行放置的合法性
bool isValid(vector<string> &cur, int &n, int row, int col);

vector<vector<string > > solveNQueens(int n) {

    // 解决方案结果集
    vector<vector<string > > res;

    // 初始化棋盘，所有的位置都没有摆放皇后
    vector<string> cur(n, string(n, '.'));
    dfs(res, cur, n, 0);
    return res;
}

/*
    res：返回的解决方案集
    cur：当前的一个解决方案
    n：n皇后问题
    row：当前解决方案的第row行
*/
void dfs(vector<vector<string > > &res, vector<string> &cur, int &n, int row) {

    // 当超出行数超出了棋盘，则把这次搜索的结果放入res中。
    if (row == n) {
        res.push_back(cur);
        return;
    }

    for (int j = 0; j < n; j++) {

        // 判断在row行j列处是否可以放一个皇后
        if (isValid(cur, n, row, j)) {

            // 如果可以，则放一个皇后在（row，j）
            cur[row][j] = 'Q';

            // 继续在下一行找一个位置放皇后
            dfs(res, cur, n, row + 1);

            // 因为需要找到所有可能的情况，所以必然需要对每一行进行回退。
            // 去判断这一行的下一列是否可以放皇后。
            cur[row][j] = '.';
        }
    }
}
/*
    cur：当前解决方案
    n：n皇后问题
    row：考虑当前解决方案的第row行
    col：考虑当前解决方案的第col行
*/
bool isValid(vector<string> &cur, int &n, int row, int col) {

    // 检查列
    for (int i = 0; i < row; i++) {
        if (cur[i][col] == 'Q') {
            return false;
        }
    }

    // 检查反斜线（\）
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (cur[i][j] == 'Q') {
            return false;
        }
    }
    // 检查斜线（/）
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (cur[i][j] == 'Q') {
            return false;
        }
    }

    return true;
}
int main()
{
    vector<vector<string > > res = solveNQueens(4);
    for(int i=0; i<res.size(); i++)
    {
        for(int j=0; j<res[0].size(); j++)
            cout<<res[i][j]<<endl;
        cout<<endl;
    }
    return 0;
}

运行结果

以上。