【小白爬Leetcode51】4.5 N皇后 N-Queens

Leetcode 51 $\color{#FF0000}{hard}$hard

题目

Discription

The n-queens puzzle is the problem of placing n queens on an n×n chessboard 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.

中文解释

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

提示：

皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。（引用自 百度百科 - 皇后 ）

思路 回溯

由题意可知，皇后可以吃掉横、竖、对角线上的所有子，因此每当放下一个皇后在棋盘上，她所在的行、列、对角线都不可以再放皇后了。
图片来源：小象学院

一个朴素的思想是：

• 从第0行开始遍历，直到最后一行，每一行k都用for循环尝试在每一列j摆放皇后；
• 根据是否在其他皇后的攻击范围内，来确定是否在该位置k,j摆放皇后。这里用到了一个mark数组（初始为n*n的0数组），来记录所有皇后的攻击范围。即从一个皇后出发，向八个方向延伸，逢0变1（表示这个位置遍历过了）。
• 如果能遍历到最后一行的下一行，即k==n说明得到了一个可行解；否则退回到上一步，重新选择皇后的摆放位置。

递归实现如下,其中：

• generate为递归函数，完成对每一行每一列的遍历；
• put_then_queen用来更新mark数组，记录新的所有皇后攻击范围；
• solveQueens主要用于初始化和最终输出结果。

class Solution {
public:
	vector<vector<string>> solveNQueens(int n) {
		vector<vector<string>> ret;
		vector<string> location; // 用来记录当前所有皇后的位置
		vector<vector<int>> mark(n, vector<int>(n, 0)); //用来记录当前所有皇后的攻击范围
		for (int i = 0; i < n; i++) {
			location.push_back("");
			location[i].append(n, '.');
		}
		generate(0, n, location, mark, ret);
		return ret;
	}
private:
	//包揽八个方向，每个方向前进一个格的扩散数组

	void put_the_Queen(int n, int x, int y, vector<vector<int>>& mark) {
        static const int dx[] = { -1,0,1,-1,1,-1,0,1 }; //分别表示了周围的8个格子x的变化
	    static const int dy[] = {  1,1,1,0,0,-1,-1,-1  };  //分别表示了周围的8个格子y的变化
		mark[x][y] = 1; //皇后本身的位置标记
		int max_step = max(x, n - 1 - x) > max(y, n - 1 - y) ? max(x, n - 1 - x) : max(y, n - 1 - y);
		for (int i = 1; i <= max_step; 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<n && new_y >= 0 && new_y<n) mark[new_x][new_y] = 1;
			}
		}
	}
	void generate(int k, int n, vector<string>& location, vector<vector<int>>& mark, vector<vector<string>>& ret) {
		//递归函数，k代表递归到第几行，n表示棋盘大小
		if (k == n) {
			ret.push_back(location);
			return;
		}
		for (int i = 0; i < n; i++) {
			if (mark[k][i] == 0) { //如果这个位置可用
				location[k][i] = 'Q';
				vector<vector<int>>temp_mark = mark;
				put_the_Queen(n, k, i, mark);
				generate(k + 1, n, location, mark, ret);
				location[k][i] = '.';
				mark = temp_mark;
			}
		}
	}
};

这个程序有值得完善的地方，因为它使用了太多的容器，每一次递归都要维护容器，尤其是mark数组，容量为n*n，每一次维护需要至多8*n次操作。因此可以对代码所用到的数据结构进行轻量化：

比较好想的是：

• 一行只有一个皇后，这就是我们一行行遍历的依据；
• 一列只有一个皇后，因此我们可以设置一个vector<int> col数组，记录每一列的第几行有皇后，如：

  col = [2,0,1,3]

代表着第0行第2列，第1行第0列，第2行第1列，第3行第3列有王后，可以根据这个数组来构建最后的结果：
形式为：

[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

很难注意到的是：

• 主对角线(dale diagonals)一共有2*n-1个，且每个对角线经过的格子，行-列=const，因此可以设置一个vector <int> dale_diagonals，用行-列来做索引。当然了，有正有负，而索引肯定要是非负数，所以可以用行-列+n-1=const来做索引；
• 副对角线(hill diagonals)一共有2*n-1个，且每个对角线经过的格子，行+列=const，因此可以设置一个vector <int> hill_diagonals，用行+列来做索引；
  
  修改后的代码为：

class Solution {
public:
	vector<vector<string>> solveNQueens(int n) {
		vector<vector<string>> ret; //结果数组
		vector<int> col(n,-1); // 行的情况
        vector<int> hill_diagonal(2*n-1,0); //主对角线情况，共有2*n-1个主对角线
        vector<int> dale_diagonal(2*n-1,0); //副对角线情况，共有2*n-1个副对角线
		generate(0, n, col,hill_diagonal,dale_diagonal,ret);
		return ret;
	}
private:
    vector<string> form_result(int n,vector<int>& col) {
        vector<string> *p = new vector<string>(n, "");
        for (int i=0; i < n; i++) {
            for (int j=0; j < n; j++) {
                if (j == i) (*p)[col[i]] += 'Q';
                else (*p)[col[i]] += '.';
            }
        }
        return *p;
    }
	void generate(int k, int n, vector<int>& col, vector<int>& hill_diagonal, vector<int>& dale_diagonal,vector<vector<string>>& ret) {
		//递归函数，k代表递归到第几行，n表示棋盘大小
		if (k == n) {
			ret.push_back(form_result(n,col));
			return;
		}
		for (int i = 0; i < n; i++) {
			if (hill_diagonal[k-i+n-1]==0 && dale_diagonal[k+i]==0 && col[i]==-1) { //如果这个位置可用
                //放置皇后
				hill_diagonal[k-i+n-1]=1;
                dale_diagonal[k+i]=1;
                col[i] = k;
                //下层递归
				generate(k + 1, n, col, hill_diagonal, dale_diagonal,ret);
				//删除皇后
                hill_diagonal[k-i+n-1]=0;
                dale_diagonal[k+i]=0;
                col[i] = -1;
			}
		}
	}
};