leetcode刷题/回溯 51. N 皇后

51. N 皇后

题意:

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

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

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
           

示例 2：

输入：n = 1
输出：[["Q"]]
           

解题思路

棋盘问题也是用暴力递归 + 回溯. 每一个位置,然后判断该位置是否可以放.遍历全部可能即可.

问	答
递归结束条件	全部行都递归完毕
单层递归	判断当前节点是否可以放值皇后,如果可以就放置递归下一行.如果不行就寻找下一个位置.
参数	因为需要直到是否到最后一行,所以需要一个标记index.
剪枝	只能在判断里剪枝

如何判断该位置是否可以放置皇后

三种情况是不可以放的:

1. 同行有女皇
2. 同列有女皇
3. 用对角线有女皇

所以判断条件可以用一个函数来完成,就如代码中的

isPrime

class Solution {
private:
    //记录结果
    vector<vector<string>> res;
    //用来记录接收,少传一个参数
    int number = 0;
public:

bool isPrime(vector<string> &num, int x, int y)
{
    //因为是递归,所以同行不可能有女皇,不需要判断同行
    
    //同列有女皇,且因为当前行一下的都还是点,所以不用判断当前层以下的
	for (int j = 0; j < x; j++)
	{
		if (num[j][y] == 'Q')
			return false;
	}
	
    //同对角线有女皇,因为当前行一下的都还是点,所以不用判断当前层以下的
	for (int i = x, j = y; i >= 0 && j >= 0; i--, j--)
	{
		if (num[i][j] == 'Q')
			return false;
	}
    
	for (int i = x, j = y; i >= 0 && j < number; i--, j++)
	{
		if (num[i][j] == 'Q')
			return false;
	}

	return true;
}

void backstract(vector<string> &num,int index)
{
    //如果当前层数已经超过最后一行,就说明找到一种可能
	if (index >= number)
	{
		res.push_back(num);
		return;
	}

    //同层遍历找可以放置皇后的地方,找到了就递归找下一层
	for (int i = 0; i < number; i++)
	{
        //判断该位置是否可以放置皇后
		if (!isPrime(num,index, i))
			continue;

        //执行到这说明可以放皇后,放置皇后
		num[index][i] = 'Q';
        //递归寻找下一层
		backstract(num, index + 1);
        //回溯
		num[index][i] = '.';
	}
}

    vector<vector<string>> solveNQueens(int n) {
    //获得阶数
	number = n;
    //创建一个棋盘
	vector<string>num(n,string(n,'.'));
    //开始递归
	backstract(num, 0);
    //返回结果
	return res;
    }
};
           

总结:

基本的回溯加上一个判断条件,该位置是否可以放女皇. 因为题目没有说明什么地方可以什么地方不可以,我是通过网上找的才知道不能同行同列同对角线.如果知道这道题就变得简单了