首页 > 代码库 > N-Queens
N-Queens
N-Queens
Total Accepted: 12866 Total Submissions: 49759My SubmissionsThe 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:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
经典的N皇后问题,这个问题采用DFS比较容易解决。
class Solution { public: vector<vector<string> > solveNQueens(int n) { ans.clear(); vector<string> puzzle; puzzle_size = n; for (int i = 0; i < n; ++i) { puzzle.push_back(string(n, '.')); } solve(puzzle, 0); return ans; } private: vector<vector<string> > ans; int puzzle_size; void solve(vector<string> &puzzle, int row) { if (row == puzzle_size) { ans.push_back(puzzle); return; } for (int i = 0; i < puzzle_size; ++i) { puzzle[row][i] = 'Q'; if (!isConflict(puzzle, row, i)) { solve(puzzle, row + 1); } puzzle[row][i] = '.'; } } bool isConflict(const vector<string> &puzzle, int row, int col) { for (int i = row - 1; i >= 0; --i) { if ('Q' == puzzle[i][col]) { return true; } int diff_col = row - i; if (col - diff_col >= 0 && 'Q' == puzzle[i][col - diff_col]) { return true; } if (col + diff_col < puzzle_size && 'Q' == puzzle[i][col + diff_col]) { return true; } } return false; } };
N-Queens
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。