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;
    }
};
           

總結:

基本的回溯加上一個判斷條件,該位置是否可以放女皇. 因為題目沒有說明什麼地方可以什麼地方不可以,我是通過網上找的才知道不能同行同列同對角線.如果知道這道題就變得簡單了