[LeetCode] 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.."]
]

用2个栈stack模拟递归bfs方法，发现stack比递归速度快很多，递归的方法在9皇后时速度特别慢，通不过，用stack就会Accept！

class Solution {
public:
   vector<vector<string> > result;

    vector<vector<string> > solveNQueens(int n) {
        vector<int> board(n+1,0);
        stack<vector<int> > s;
        s.push(board);        
        return  totalN(n,s);

    }
private:
    vector<vector<string> > totalN(int n,stack<vector<int> > s){
        
        int k = 1;
        while(k<=n){
            stack<vector<int> > s0;
            while(!s.empty()){
                vector<int> board = s.top();
                vector<int>  board0(board);
                s.pop();

                for(int i=1;i<=n;i++){
                    board[k]=i;
                    if(isok(k,board)){
                        s0.push(board);    
                    }
                    board = board0;
                }

            }
            k++;
            s = s0;
        }

        while(!s.empty()){
            string s0(n,'.');
            vector<string> vs(n,s0);
            vector<int> board = s.top();
            s.pop();
            for(int i=1;i<=n;i++){
                vs[i-1][board[i]-1]='Q';
            }
            result.push_back(vs);
        }
        return result;
    }
    bool isok(int k,vector<int> &board){//check whether the ktn Queen can be put down
        for(int i=1;i<k;i++){
            if(board[i]==board[k]||abs(i-k)==abs(board[i]-board[k]))
                return false;
        }
        return true;
    }
};