Leetcode:51. N-Queens

Description

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

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

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

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

思路

• 按照劍指offer上比較low的思路，先將所有的排列求出來，然後判斷每個排列是否滿足條件
• 遞歸方式

代碼

• 求出所有排列後判斷

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        if(n == 0) return res;
        
        vector<int> nums(n);
        for(int i = 0; i < n; ++i)
            nums[i] = i;
            
        do{
            if(isValid(nums, n)){
                vector<string> str;
                 generate(nums, n, str);
                 res.push_back(str);
            }
        }while(getNextPermutation(nums, n));
        
        return res;
    }

private:
    bool getNextPermutation(vector<int> &nums, int len){
        int index1 = 0, index2 = -1, flag = -1;
        for(int i = 1; i < len; ++i){
            if(nums[i] > nums[i - 1]){
                index1 = i - 1;
                index2 = i;
                flag = nums[i] - nums[i - 1];
            }
            else if(nums[i] > nums[index1] && nums[i] - nums[index1] < flag){
                index2 = i;
                flag = nums[i] - nums[index1];
            }
        }
        
        if(index2 == -1) return false;
        swap(nums[index1], nums[index2]);
        sort(nums.begin() + index1 + 1, nums.end());
        return true;
    }
    
    bool isValid(vector<int> &nums, int len){
        for(int i = 0; i < len; ++i){
            for(int j = i + 1; j < len; ++j){
                if(i - j == nums[i] - nums[j] || j - i == nums[i] - nums[j])
                    return false;
            }
        }
        
        return true;
    }
    
    void generate(vector<int>& nums, int len, vector<string> &str){
        for(int i = 0; i < len; ++i){
            string tmp(len, '.');
            tmp[nums[i]] = 'Q';
            str.push_back(tmp);
        } 
    }
};

• 遞歸。Accepted 4ms c++ solution use backtracking and bitmask, easy understand.

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        if(n == 0) return res;
        
        vector<string> nums(n, string(n, '.'));
        
        solve(res, nums, n, 0);
        
        return res;
    }

private:
    void solve(vector<vector<string>> &res, vector<string> &nums, int n, int rows){
       if(rows == n){
           res.push_back(nums);
           return;
       }
       
       for(int cols = 0; cols < n; ++cols){
           if(isValid(nums, rows, cols, n)){
               nums[rows][cols] = 'Q';
               solve(res, nums, n, rows + 1);
               nums[rows][cols] = '.';
           }
       }
    }
    
    bool isValid(vector<string> &nums, int rows, int cols, int n){
        for(int i = 0; i != rows; ++i){
           if(nums[i][cols] == 'Q')
                return false;
        }
        
        for(int i = rows- 1, j = cols - 1; i >= 0 && j >= 0; --i, --j)
            if(nums[i][j] == 'Q')
                return false;
                
        for(int i = rows - 1, j = cols + 1; i >= 0 && j < n; --i, ++j)
            if(nums[i][j] == 'Q')
                return false;
        
        return true;
    }
    
};