首页 > 代码库 > N-Queens

N-Queens

2024-08-29 22:01:05   219人阅读

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:

分析： 著名的N皇后问题，可以采用一位数组来代替二维数组，利用回溯，注意皇后行走的条件

class Solution {
public:
    bool isOk(int start,int value, const vector<int>& array){
        for(int i =start-1; i>=0; i--)
            if((array[i]==value) || (abs(array[i]-value)==abs(start-i)))
                return false;
        if(abs(array[start-1]-value)==1)
            return false;
        return true;
    }
    void Queen(int start, vector<int>& array, vector<vector<int>> & res ){
        //cout << start <<endl;
        if(start == array.size()){
            res.push_back(array);
            return;
        }
       for(int i =0; i< array.size(); i++){
           if(isOk(start, i, array)){
              // cout <<"hello"<<endl;
               array[start] =i;
               Queen(start+1, array, res);
           }
           
       }
       return;
    }
    
    void convert(const vector<vector<int>> res, vector<vector<string>>& str){
        for(vector<int> t: res){
            int n = t.size();
            vector<string> strlist;
            for(int i=0; i<n; i++){
                string s(n,‘.‘);
                s[t[i]] = ‘Q‘;
                strlist.push_back(s);
            }
            str.push_back(strlist);
            
        }
        
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<int>> res;
        vector<vector<string>> str;
        if(n==0)
            return str;
        vector<int> array(n,0);
        for(int i =0; i< n; i++){
            array[0] =i;
            Queen(1,array,res);
        }
        convert(res,str);
        return str;
        
    }
};

　　

N-Queens


联系
我们