欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

八皇后问题

程序员文章站 2022-04-22 11:01:30
...

八皇后问题
八皇后问题
八皇后问题,太经典了。这儿记录一个回溯写法。回溯法适用于求解含有多个步骤的问题,且每个步骤都有多个选择,每次我们只选一个选择去求解,若达到解的条件则为一个解,若无解那么回到上一步换一个选择继续求解。
八个皇后在水平竖直对角方向都不能共线,那这肯定作为求解过程中的限制。我们用一个数组记录每个皇后在对应行上的位置。假设棋盘有n格,每个皇后就有n个选择,每次选一个,然后判断该皇后在这儿会不会与已有皇后冲突,若不冲突,那么继续放下一行的皇后。当n个皇后都放好了就按照题目要求输出就好了。

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        
        vector<vector<string>> res;
        if (n<=0) return res;
        vector<int> tmp(n,0); // 记录一个可行解,数组每个位置记录皇后在i行的位置
        helper(n,0,tmp,res);
        return res;
    }
    
    // 找可行解
    void helper(int n, int row,vector<int>& tmp, vector<vector<string>>& res)
    {
        if(row==n)
        {
            //for (auto x: tmp) cout<<x<<" ";
            //cout<<endl;
            vector<string> s=decode(tmp,n);
            res.push_back(s);
            
        }
        else
        {
            // 每个皇后有n个选择
            for (int i=0;i<n;i++)
            {
                tmp[row]=i;
                //检查这么放会不会和已有皇后冲突
                if (check(row,i,n,tmp))
                {
                    helper(n,row+1,tmp,res);
                }
            }
        }
        
    }
    bool check(int row,int col,int n, vector<int> tmp)
    {
        int leftUp=col-1,rightUp=col+1;
        for (int i=row-1;i>=0;i--)
        {
            if (tmp[i]==col) return false;
            if (leftUp>=0&&leftUp==tmp[i]) return false;
            if (rightUp<n&&rightUp==tmp[i]) return false;
            leftUp--;
            rightUp++;
        }
        return true;
    }
    // 对皇后位置解码乘输出格式
    vector<string> decode(vector<int> tmp,int n)
    {
        vector<string> res;
        int count=n;
        for (auto x: tmp)
        {
            count=n;
            string str="";
            while(count-->0) str+='.';
            str[x]='Q';
            res.push_back(str);
        }
        return res;
    }
};