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:

分析： 著名的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

最新文章

热门文章