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 the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown below. [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
Solution: DFS
Time complexity: O(n!)
Space complexity: O(n)
C++
|
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 |
// Author: Huahua class Solution { public: int totalNQueens(int n) { vector<int> cols(n); vector<int> diag1(2 * n - 1); vector<int> diag2(2 * n - 1); int ans = 0; function<void(int)> dfs = [&](int r) { if (r == n) { ++ans; return; } for (int i = 0; i < n; i++) { int& c = cols[i]; int& d1 = diag1[r + i]; int& d2 = diag2[r - i + n - 1]; if (c || d1 || d2) continue; c = d1 = d2 = 1; dfs(r + 1); c = d1 = d2 = 0; } }; dfs(0); return ans; } }; |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment