Day17-递归&回溯-N皇后

BUPTrenyi

发布于 2019-07-15 08:59:49

44600

代码可运行

文章被收录于专栏：算法其实很好玩算法其实很好玩

运行总次数：0

代码可运行

一唠嗑

我昨天那么勤奋的更了两篇文章，为啥大家只看第一篇？？？

那以后我就更一篇好了

二开讲！

Q：1848年，国际象棋棋手，马克思·贝瑟尔，提出了赫赫有名的八皇后问题：

国际象棋8x8的棋盘，皇后棋子的该行，该列，两条对角线上，均不能再放置皇后棋子。那么放置8个皇后，最多有多少种摆法？

我们今天要解决的是泛类问题，即NxN的棋盘上，摆N个皇后，有几种摆法，分别怎么摆？

三冷静分析

我们可以这样处理思路：

1.首先我们需要知道，NxN的棋盘，最多放N个皇后，且每行都有且仅有一个皇后。

2.知道这一点后，我们可以这样处理：

（1）建立一个二维数组，0表示该位置可以放皇后，1表示该位置不能放皇后，初始全为0；

（2）保存放入皇后前棋盘的位置信息作为镜像，便于回溯时，选择其他的位置信息。从第一行开始，这个皇后有N列可以选择，选择一列后，放入皇后。更新棋盘的位置信息，即，该行，该列，和两条对角线上，均不能再放置皇后；

（3）那我们就把皇后的位置，以及该皇后放入后，不能再放入皇后的位置，置1；

（4）递归处理下一行，即重复（2）（3）步骤

（5）一行一行往下递归，当发现还没到最后一行时，此时棋盘上已无法再放入皇后，则进行回溯，根据之前的镜像棋盘信息，再选择其他的位置，放入皇后，再进行递归。

（6）什么时候递归终止呢？当遍历到第n+1行，即超出了边界，我们认为前面的皇后都合法放入了，这就是一种摆法，将其添加进result，一层一层return，直到递归入口，改变递归处初始皇后位置，再次重复前面的递归&回溯过程。

（7）什么时候退出函数返回最终结果呢？即初始递归入口处，就已经到n+1行了，这时已经全部求出所有N皇后摆法，返回最终结果。

四完整代码及十分详细的注释

//
// Created by renyi on 2019/6/27.
//
#include <iostream>
#include <vector>
#include <string>
using namespace std;

void LocationOccupiedByQueen(int x, int y, vector<vector<int>> &chess){//定义函数，求出第x行，第y列放置皇后之后，该皇后占用的位置，即8个方向的位置，占位用1表示
    static const int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};//单位方向数组，分别表示，上，下，左，右，左上，左下，右上，右下
    static const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
    chess[x][y] = 1;//皇后的位置，置1
    for (int i = 1; i < chess.size(); i++) {
        for (int j = 0; j < 8; j++) {//对8个方向的位置进行占位操作
            int new_x = x + i * dx[j];
            int new_y = y + i * dy[j];

            if (new_x >= 0 && new_x < chess.size() && new_y >= 0 && new_y < chess.size()){
                chess[new_x][new_y] = 1;
            }
        }
    }
}

//定义函数，k表示正在处理第k行的皇后，一共n列，location代表皇后的摆放位置，chess代表皇后的占位，result代表最终结果
void placeQueens(int k, int n, vector<string> &location, vector<vector<string>> &result, vector<vector<int>> &chess){
    if (k == n){//第n行下标n-1，已经处理到第n+1行，即都处理完了
        result.push_back(location);
        return;
    }

    for (int i = 0; i < n; i++) {//对于每一行的皇后，都有n列可能放置
        if (chess[k][i] == 0){
            vector<vector<int>> temp_chess = chess;//保存此时棋盘上皇后的占位情况，便于回溯至此
            location[k][i] = 'Q';//字符串数组location，皇后的位置放入Q
            LocationOccupiedByQueen(k, i, chess);//棋盘数组chess，将k行i列放入皇后
            placeQueens(k + 1, n, location, result, chess);//递归到下一行，依然有n列可能放入皇后
            chess = temp_chess;//递归回溯至此时，恢复当时的棋盘数组
            location[k][i] = '#';//将当前皇后位置重新置#号，再次尝试
        }
    }
}

//定义最终在main函数中调用的函数，NQueens，返回二维字符串数组
vector<vector<string>> NQueens(int n){//参数为n，n是几，就是几皇后
    vector<vector<string>> result;
    vector<string> location;
    vector<vector<int>> chess;

    for (int i = 0; i < n; i++) {
        chess.push_back((vector<int>()));//棋盘数组初始是n x n的0
        for (int j = 0; j < n; j++) {
            chess[i].push_back(0);
        }
        location.push_back("");
        location[i].append(n, '#');//在字符串末尾追加n个’#‘
    }
    placeQueens(0, n, location, result, chess);
    return result;
}

int main(){
    vector<vector<string>> result;
    result = NQueens(4);
    for (int i = 0; i < result.size(); i++) {
        printf("i = %d\n", i);
        for (int j = 0; j < result[i].size(); j++) {
            printf("%s\n", result[i][j].c_str());
        }
        printf("\n");
    }
    return 0;
}