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

1 vector
     
      
        > result; 2     vector
       
        
          > solveNQueens(int n)  3     { 4         if (n <= 0) 5             return result; 6         vector
         
           mark(n, 0); 7          8         NQueen(mark, n, 0); 9         return result;10     }11     12     void NQueen(vector
          
            &mark, int n, int row)13 {14 if (row == n) // get a solution15 {16 vector
           
             strRow;17 for (int i = 0; i < n; i++)18 {19 string str;20 for (int j = 0; j < n; j++)21 if (mark[i] == j)22 str.push_back('Q');23 else24 str.push_back('.');25 strRow.push_back(str);26 }27 result.push_back(strRow);28 return;29 }30 31 for (int i = 0; i < n; i++)32 {33 mark[row] = i;34 if (check(mark, row))35 NQueen(mark, n, row + 1);36 }37 }38 39 bool check(vector
            
              mark, int row)40 {41 for (int i = 0; i < row; i++)42 {43 if (mark[i] == mark[row] || abs(mark[i] - mark[row]) == (row - i))44 return false;45 }46 return true;47 }