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

发布时间：2020-12-14 05:10:17 所属栏目：百科来源：网络整理

导读：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: 4Output:

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",?// 解法 2
? "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,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]],_ 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,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,&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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!