Problem:
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:
1 2 3 4 5 6 7 8 9 10 11 |
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] |
Idea:
Search
Solution:
Changes: 12/20/2017
type of sols_ changed from set<vector<string>> to vector<vector<string>>. Thanks to Yun-Ting Lin.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
// Author: Huahua // Runtime: 3 ms class Solution { public: vector<vector<string>> solveNQueens(int n) { sols_.clear(); board_ = vector<string>(n, string(n, '.')); cols_ = vector<int>(n, 0); diag1_ = vector<int>(2 * n - 1, 0); diag2_ = vector<int>(2 * n - 1, 0); nqueens(n, 0); return sols_; } private: vector<string> board_; vector<int> cols_; vector<int> diag1_; vector<int> diag2_; vector<vector<string>> sols_; bool available(int x, int y, int n) { return !cols_[x] && !diag1_[x + y] && !diag2_[x - y + n - 1]; } void updateBoard(int x, int y, int n, bool is_put) { cols_[x] = is_put; diag1_[x + y] = is_put; diag2_[x - y + n - 1] = is_put; board_[y][x] = is_put ? 'Q' : '.'; } // Try to put the queen on y-th row void nqueens(const int n, const int y) { if (y == n) { // found one solution, add to the ans set sols_.push_back(board_); return; } // Try every column for (int x = 0; x < n; ++x) { if (!available(x, y, n)) continue; updateBoard(x, y, n, true); nqueens(n, y + 1); updateBoard(x, y, n, false); } } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment