采用回溯法,以行为基准进行回溯,如果在当前行列放置皇后不会与已有皇后冲突,则放置,否则就不放置。
代码如下:
// // Created by jt on 2020/9/29. // #include <vector> using namespace std; class Solution { public: vector<vector<string> > solveNQueens(int n) { vector<vector<string>> res; vector<int> vec; backtrace(res, vec, 0, n); return res; } void backtrace(vector<vector<string>> &res, vector<int> vec, int row, int n) { if (row == n) { vector<string> tmp; for (auto a : vec) { string s = string(n, '.'); s[a] = 'Q'; tmp.push_back(s); } res.push_back(tmp); return; } for (int col = 0; col < n; ++col) { vec.push_back(col); if (!detectConflict(vec)) backtrace(res, vec, row+1, n); vec.pop_back(); } } bool detectConflict(vector<int> &vec) { int curRow = vec.size() - 1, curCol = vec[vec.size()-1]; for (int row = 0; row < vec.size() - 1; ++row) { // 判断是否同一直线上 if (vec[row] == curCol) return true; // 判断是否在左侧或右侧斜线上 if (curRow - row == abs(curCol - vec[row])) return true; } return false; } };