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.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

还是思维不够清晰，试了好多次才试对，代码里注释掉的部分复杂度太高，不能通过。

把棋盘存储为一个N维数组a[N]，数组中第i个元素的值代表第i行的皇后位置，这样便可以把问题的空间规模压缩为一维O(N)，在判断是否冲突时也很简单，首先每行只有一个皇后，且在数组中只占据一个元素的位置，行冲突就不存在了，其次是列冲突，判断一下是否有a[i]与当前要放置皇后的列j相等即可。至于斜线冲突，通过观察可以发现所有在斜线上冲突的皇后的位置都有规律即它们所在的行列互减的绝对值相等，即| row – i | = | col – a[i] | 。这样某个位置是否可以放置皇后的问题已经解决。

class Solution {
private:
    vector<vector<string>> res;
public:
    bool isLegal(vector<string> &temp, int row, int col)
    {
         //列
        for(int i = 0; i < row; i++)
            if(temp[i][col] == 'Q')return false;
        //右对角线
        for(int i = row-1, j=col-1; i >= 0 && j >= 0; i--,j--)
            if(temp[i][j] == 'Q')return false;
        //左对角线
        for(int i = row-1, j=col+1; i >= 0 && j < temp.size(); i--,j++)
            if(temp[i][j] == 'Q')return false;
        return true;
     }
   /* bool isLegal(vector<string> &temp,int H,int W)
    {
        for(int j=0;j<H;j++)
            for(int i=0;i<=W;i++)
            {
                if(temp[j][i]=='Q'&&(abs(j-H)==abs(i-W)||i==W))
                   return false;
            }
        return true;
    }*/
    void procedure(vector<string> &temp,int rows)
    {
        if(rows==temp.size())
        {
            res.push_back(temp);
            return;
        }
        for(int cols=0;cols<temp.size();cols++)
        {  if(isLegal(temp,rows,cols))
            {
              temp[rows][cols]='Q';
              procedure(temp,rows+1);
              temp[rows][cols]='.';
            }
        }
        return ;
    }
    vector<vector<string> > solveNQueens(int n) {
        if(n==1)
        {   
            vector<string> t1(1,"Q");
            vector<vector<string>> res1(1,t1);
            return res1;
        }
        if(n<4)
        {
           vector<vector<string>> res2;
           return res2;
        }
       vector<string> temp(n,string(n,'.'));
       procedure(temp,0);
       return res;       
    }
   
};