[Swift]LeetCode52.N皇后II|N-QueensII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9910438.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.."]
]

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

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

示例:

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

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

8ms

 1 class Solution {
 2     func totalNQueens(_ n: Int) -> Int {
 3         if n == 0 {
 4             return 0
 5         }
 6         var answer = 0
 7         var limit = (1<<n) - 1
 8         dfs(h: 0, r: 0, l: 0, answer: &answer, limit: &limit)
 9         return answer
10     }
11     private func dfs(h: Int, r: Int, l: Int, answer: inout Int, limit: inout Int) {
12         if h == limit {
13             answer += 1
14             return
15         }
16         var position = limit & (~(h|r|l))
17         while position > 0 {
18             let p = position & (-position)
19             position -= p
20             dfs(h: h+p, r: (r+p)<<1, l: (l+p)>>1, answer: &answer, limit: &limit)
21         }
22     }
23 }

20ms

 1 class Solution {
 2     var placeArr : [Int]!
 3     var totalN : Int = 0
 4     func canPlace(_ row:Int , _ col:Int) -> Bool{
 5 
 6         var colInRow : Int = 0
 7         var offset : Int = 0
 8         for idx in 0 ..< row {
 9             colInRow = placeArr[idx]
10            
11             if colInRow == col {
12                 return false
13             }
14             offset = row - idx
15             if colInRow == col - offset{
16                 return false
17             }
18             if colInRow == col + offset{
19                 return false
20             }
21         }
22         return true
23     }
24     
25     var count : Int = 0
26     func place(_ row:Int) -> (){
27         if row == totalN {
28             count += 1
29         }else{
30             for col in 0..<totalN {
31                 if canPlace(row,col) {
32                     placeArr[row] = col
33                     place(row + 1)
34                 }
35             }
36         }
37     }
38     
39     func totalNQueens(_ n: Int) -> Int {
40         totalN = n
41         placeArr = Array(repeating : 0 , count : totalN)
42         
43         place(0)
44         return count
45     }
46 }

28ms

 1 class Solution {
 2     func totalNQueens(_ n: Int) -> Int {
 3         var board = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n)
 4         var result = 0
 5         backtrack(&board, 0, &result)
 6         return result
 7     }
 8     
 9     private func backtrack(_ board: inout [[Bool]], _ row: Int, _ result: inout Int) {
10         if row == board.count {
11             result += 1
12         } else {
13             for col in 0..<board.count where canPlaceQueen(board, row, col) {
14                 board[row][col] = true
15                 backtrack(&board, row + 1, &result)
16                 board[row][col] = false
17             }
18         }
19     }
20     
21     private func canPlaceQueen(_ board: [[Bool]], _ row: Int, _ col: Int) -> Bool {
22         let n = board.count
23         
24         for i in 0..<row where board[i][col] {
25             return false
26         }
27         
28         var i = row - 1
29         var j = col - 1
30         while i >= 0 && j >= 0 {
31             if board[i][j] {
32                 return false
33             }
34             i -= 1
35             j -= 1
36         }
37         
38         i = row - 1
39         j = col + 1
40         while i >= 0 && j < n {
41             if board[i][j] {
42                 return false
43             }
44             i -= 1
45             j += 1
46         }
47         
48         return true
49     }
50 }

32ms

 1 class Solution {
 2     var placeArr : [Int]!
 3     var totalN : Int = 0
 4     func canPlace(_ row:Int , _ col:Int) -> Bool{
 5 
 6         var colInRow : Int = 0
 7         var offset : Int = 0
 8         for idx in 0 ..< row {
 9             colInRow = placeArr[idx]
10            
11             if colInRow == col {
12                 return false
13             }
14             offset = row - idx
15             if colInRow == col - offset{
16                 return false
17             }
18             if colInRow == col + offset{
19                 return false
20             }
21         }
22         return true
23     }
24     
25     var count : Int = 0
26     func place(_ row:Int) -> (){
27         if row == totalN {
28             count += 1
29         }else{
30             for col in 0..<totalN {
31                 if canPlace(row,col) {
32                     placeArr[row] = col
33                     place(row + 1)
34                 }
35             }
36         }
37     }
38     
39     func totalNQueens(_ n: Int) -> Int {
40         totalN = n
41         placeArr = Array(repeating : 0 , count : totalN)
42         
43         place(0)
44         return count
45     }
46 }

44ms

 1 class Solution {
 2     
 3     func totalNQueens(_ n: Int) -> Int {
 4         var result = 0
 5         var cols = [Int]()
 6         cols.reserveCapacity(n)
 7         queensDFS(n, &cols, &result)
 8         return result
 9     }
10     
11     fileprivate func queensDFS(_ n: Int, _ cols: inout [Int], _ counter: inout Int) {
12         if cols.count == n {
13             counter += 1
14             return 
15         }
16         
17         for colIndex in 0..<n {
18             guard isValid(cols, colIndex) else {
19                 continue
20             }
21             cols.append(colIndex)
22             queensDFS(n, &cols, &counter)
23             cols.removeLast()
24         }
25     }
26     
27     fileprivate func isValid(_ cols: [Int], _ colIndex: Int) -> Bool {
28         for rowIndex in 0..<cols.count {
29             if colIndex == cols[rowIndex] {
30                 return false
31             }
32             if abs(colIndex - cols[rowIndex]) == abs(cols.count - rowIndex) {
33                 return false
34             }
35         }
36         return true
37     }
38 }