0051._ N-Queens.md

51. N-Queens

难度:Hard

刷题内容

原题连接

• https://leetcode.com/problems/n-queens/

内容描述

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.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

思路1 - 时间复杂度: O(2^n)- 空间复杂度: O(n)******

用回溯法去解这题。遇到合适的就继续搜索，不合适的就回退，这里用三个数组分别记录竖直方向，右斜上方和左斜上方是否有皇后。

class Solution {
public:
    void travel(int* d,vector<string>& ret,int level,int n,vector<vector<string> >& ans,int* l,int* r)
    {
        if(level >= n)
            ans.push_back(ret);
        for(int i = 0;i < n;++i)
            if(!d[i] && !r[level + i] && !l[i - level + n])
            {
                d[i] = 1;
                r[level + i] = 1;
                l[i- level + n] = 1;
                ret[level][i] = 'Q';
                travel(d,ret,level + 1,n,ans,l,r);
                d[i] = 0;
                r[level + i] = 0;
                l[i- level + n] = 0;
                ret[level][i] = '.';
            }
    }
    vector<vector<string>> solveNQueens(int n) {
        int d[n];
        int l[2 * n];
        int r[2 * n];
        memset(d,0,sizeof(d));
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        vector<string> temp;
        vector<vector<string> > ans;
        string s(n,'.');
        for(int i = 0;i < n;++i)
            temp.push_back(s);
        for(int i = 0;i < n;++i)
        {
            temp[0][i] ='Q';
            d[i] = 1;
            r[i] = 1;
            l[i + n] = 1;
            travel(d,temp,1,n,ans,l,r);
            temp[0][i] = '.';
            d[i] = 0;
            r[i] = 0;
            l[i + n] = 0;
        }
        return ans;
    }
};