LeetCode：N皇后

朴灿烈づ我的快乐病毒、 2021-11-11 05:28 294阅读 0赞

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。  
![在这里插入图片描述][20190804135824382.png]  
上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:
    
    输入: 4
    输出: [
     [".Q..",  // 解法 1
      "...Q",
      "Q...",
      "..Q."],
    
     ["..Q.",  // 解法 2
      "Q...",
      "...Q",
      ".Q.."]
    ]
    解释: 4 皇后问题存在两个不同的解法。

class Solution {
    public:
        vector<vector<string>>  res;
        int N = 0;
        string row_str = "";
        int Queen[100] = {0};
        vector<vector<string>> solveNQueens(int n) {
            N = n;
            for(int i = 0; i < N; i++)
                row_str += ".";
            back_tracking(0);
            return res;
        }
        int back_tracking(int row = 0)
        {
            if(row == N)
            {
                vector<string> temp;
                for(int i = 0 ; i < N; i++)
                {
                    string str = row_str;
                    str[Queen[i]] = 'Q';
                    temp.push_back(str);
                }
                res.push_back(temp);
                return 0;
            }
            for(int col = 0; col < N; col ++)
            {
                Queen[row] = col;
                if(is_ok(row))
                    back_tracking(row + 1);
            }
            return 0;
        }
        bool is_ok(int row)
        {
            for(int j = 0; j < row; j++)
            {
                if(Queen[row] == Queen[j] || \ //同列
                    row - Queen[row] == j - Queen[j] || \
                    row + Queen[row] == j + Queen[j])
                    return false;
            }
            return true;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]

[20190804135824382.png]: /images/20211109/6c157e27f17f40a0a252d907779050d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]: /images/20211109/bbdba0faddd64aa3a1a0b0c4b50d5098.png