N-Queens

Question：
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.."]
]
 
Anwser 1：      
[cpp]  
class Solution {  
public:  
    bool check(int row, int* colArray) {  
        for (int i = 0; i < row; ++i)   
        {  
            int diff = abs(colArray[i] - colArray[row]);      // in a col  
            if (diff == 0 || diff == row - i) {         // int a row or line  
                return false;  
            }  
        }  
        return true;  
    }  
      
    void placeQueens(int row, int n, int &count, int* colArray, vector< vector<string> > &ret2) {  
        if (row == n) {  
            ++count;  
              
            vector<string> tmpRet;  
            for(int i = 0; i < row; i++){  
                string str(n, '.');  
                str[colArray[i]] = 'Q';  
                tmpRet.push_back(str);  
            }  
            ret2.push_back(tmpRet);  
            return;  
        }  
          
        for (int col = 0; col < n; ++col) {     // in 0 row, test n col  
            colArray[row] = col;  
            if (check(row, colArray)){  
                placeQueens(row+1, n, count, colArray, ret2);    // test other rows  
            }  
        }  
    }  
      
    vector<vector<string> > solveNQueens(int n) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        int *colArray = new int[n];  
        int count = 0;  
          
          
        vector< vector<string> > ret;  
        placeQueens(0, n, count, colArray, ret);  
          
        return ret;  
    }  
};  
 

补充：软件开发 , C++ ,

上一个：组合数求模C(n,m)%(10^10)
下一个：Add Two Numbers