[Swift]LeetCode51.N皇后|N-Queens

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

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

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9910395.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 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.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

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

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

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

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

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

24ms

 1 class Solution {
 2     func solveNQueens(_ n: Int) -> [[String]] {
 3         guard n > 0 else {
 4             return []
 5         }
 6         var results = [[String]]()
 7         var cols = [Int]()
 8         cols.reserveCapacity(n)
 9         dfsHelper(n, &cols, &results)
10         return results
11     }
12     
13     fileprivate func dfsHelper(_ n: Int, _ cols: inout [Int], _ results: inout [[String]]) {
14         if cols.count == n {
15             results.append(draw(cols))
16             return 
17         }
18         
19         for i in 0..<n {
20             guard isValid(cols, i) else {
21                 continue
22             }
23             cols.append(i)
24             dfsHelper(n, &cols, &results)
25             cols.removeLast()
26         }
27     }
28     
29     
30     fileprivate func isValid(_ cols: [Int], _ colIndex: Int) -> Bool {
31         for rowIndex in 0..<cols.count {
32             if colIndex == cols[rowIndex] {
33                 return false
34             }
35             if cols.count - rowIndex == colIndex - cols[rowIndex] {
36                 return false
37             }
38             if rowIndex - cols.count == colIndex - cols[rowIndex] {
39                 return false
40             }
41         }
42         return true
43     }
44     
45     fileprivate func draw(_ cols: [Int]) -> [String] {
46         var result = [String]()
47         for rowIndex in 0..<cols.count {
48             var row = ""
49             for j in 0..<cols.count {
50                 row += cols[rowIndex] == j ? "Q" : "."
51             }
52             result.append(row)
53         }
54         return result
55     }
56 }

48ms

 1 class Solution {
 2     func solveNQueens(_ n: Int) -> [[String]] {
 3         var result = [[String]]()
 4         var currB = Array(repeating:String(Array(repeating:".",count:n)),count:n)
 5         var cols = Array(repeating:false,count:n)
 6         var diagnal = Array(repeating:false,count:2*n-1)
 7         var antidiagonal = Array(repeating:false,count:2*n-1)
 8     
 9         helper(&result,&currB,n,0,&cols,&diagnal,&antidiagonal)
10         return result
11     }
12     
13     func helper(_ result: inout [[String]], _ currB: inout [String], _ n: Int, _ row: Int, _ cols: inout [Bool], _ diagonal: inout [Bool], _ antiDiagonal: inout [Bool]) -> Void {
14     
15 
16         if(row==n) {
17             result.append(currB)
18             return
19         }
20 
21         for col in 0..<n {
22             if(cols[col] || diagonal[row-col+n-1] || antiDiagonal[row+col]) {
23                 continue
24             }
25         
26             var curr = currB
27 
28         
29             cols[col] = true
30             diagonal[row-col+n-1] = true
31             antiDiagonal[row+col] = true
32         
33             curr[row] = String(curr[row].prefix(col)) + String("Q") + String(curr[row].dropFirst(col + 1))
34             helper(&result,&curr,n,row+1,&cols,&diagonal,&antiDiagonal)
35             cols[col] = false
36             diagonal[row-col+n-1] = false
37             antiDiagonal[row+col] = false
38             curr[row] = String(curr[row].prefix(col)) + String(".") + String(curr[row].dropFirst(col + 1))
39         }
40     
41         return
42     }
43 }

52ms

 1 class Solution {
 2     func solveNQueens(_ n: Int) -> [[String]] {
 3         var result = [[String]]()
 4         var answer = [String]()
 5         nQueens(n: n, p: 0, l: 0, m: 0, r: 0, answer: &answer, result: &result)
 6         return result
 7     }
 8     
 9      private func getNq(index: Int, n: Int) -> String {
10         var charArr = [Character](repeating: ".", count: n)
11         charArr[index] = "Q"
12         return String(charArr)
13     }
14     
15     private func nQueens(n: Int, p: Int, l: Int, m: Int, r: Int, answer: inout [String], result: inout [[String]]) {
16         if p >= n {
17             result.append(answer)
18             return
19         }
20         let mask = l | m | r
21         var i = 0
22         var b = 1
23         while i < n {
24             if mask & b == 0 {
25                 answer.append(getNq(index: i, n: n))
26                 nQueens(n: n, p: p+1, l: (l | b) >> 1, m: m | b, r: (r | b) << 1, answer: &answer, result: &result)
27                 answer.removeLast()
28             }
29             i += 1
30             b <<= 1
31         }
32     }
33 }

56ms

 1 class Solution {
 2     func solveNQueens(_ n: Int) -> [[String]] {
 3         var res = [[String]]()
 4         var curr = Array(repeating: 0, count: n)
 5         var usedColumn = Array(repeating: false, count: n)
 6         var usedDiagonals = Array(repeating: false, count: n * 2 - 1)
 7         var usedRevDiagonals = Array(repeating: false, count: n * 2 - 1)
 8         generateSolution(n , 0, &curr, &res, &usedColumn, &usedDiagonals, &usedRevDiagonals)
 9         return res
10     }
11     
12     
13     private func generateSolution(_ n: Int, _ row: Int, _ curr: inout [Int], _ res: inout [[String]], _ usedColumn: inout [Bool], _ usedDiagonals: inout [Bool], _ usedRevDiagonals: inout [Bool]) {
14         if row == n {
15             res.append(toList(n, curr))
16             return
17         }
18         
19         for i in 0..<n {
20             if isValid(n, row, i, usedColumn, usedDiagonals, usedRevDiagonals) {
21                 mark(n, row, i, &usedColumn, &usedDiagonals, &usedRevDiagonals)
22                 curr[row] = i
23                 generateSolution(n , row + 1, &curr, &res, &usedColumn, &usedDiagonals, &usedRevDiagonals)
24                 unMark(n, row, i, &usedColumn, &usedDiagonals, &usedRevDiagonals)
25             }
26         }
27     }
28     
29     
30     private func mark(_ n: Int, _ row: Int, _ column: Int, _ usedColumn: inout [Bool], _ usedDiagonals: inout [Bool], _ usedRevDiagonals: inout [Bool]) {
31         usedColumn[column] = true
32         usedDiagonals[row + column] = true
33         usedRevDiagonals[row - column + n - 1] = true
34     }
35     
36     
37     private func unMark(_ n: Int, _ row: Int, _ column: Int, _ usedColumn: inout [Bool], _ usedDiagonals: inout [Bool], _ usedRevDiagonals: inout [Bool]) {
38         usedColumn[column] = false
39         usedDiagonals[row + column] = false
40         usedRevDiagonals[row - column + n - 1] = false
41     }
42     
43     
44     private func isValid(_ n: Int, _ row: Int, _ column: Int, _ usedColumn: [Bool], _ usedDiagonals: [Bool], _ usedRevDiagonals: [Bool]) -> Bool {
45         return !usedColumn[column] && !usedDiagonals[row + column] && !usedRevDiagonals[row - column + n - 1]
46     }
47     
48     
49     private func toList(_ n: Int, _ curr: [Int]) -> [String] {
50         var res = [String]()
51         for num in curr {
52             var tmp = Array(repeating: ".", count: n)
53             tmp[num] = "Q"
54             var string = String()
55             for s in tmp {
56                 string += s
57             }
58             res.append(string)
59         }
60         return res
61     }
62 }

68ms

 1 class Solution {
 2     func solveNQueens(_ n: Int) -> [[String]] {
 3         var board = [[Character]](repeating: [Character](repeating: ".", count: n), count: n)
 4         var result = [[String]]()
 5         backtrack(&board, 0, &result)
 6         return result
 7     }
 8     
 9     private func backtrack(_ board: inout [[Character]], _ row: Int, _ result: inout [[String]]) {
10         if row == board.count {
11             result.append(board.map { String($0) })
12         } else {
13             for col in 0..<board.count where canPlaceQueen(board, row, col) {
14                 board[row][col] = "Q"
15                 backtrack(&board, row + 1, &result)
16                 board[row][col] = "."
17             }
18         }
19     }
20     
21     private func canPlaceQueen(_ board: [[Character]], _ row: Int, _ col: Int) -> Bool {
22         let n = board.count
23         
24         for i in 0..<row where board[i][col] == "Q" {
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] == "Q" {
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] == "Q" {
42                 return false
43             }
44             i -= 1
45             j += 1
46         }
47         
48         return true
49     }
50 }

224ms

 1 class Solution {
 2     func solveNQueens(_ n: Int) -> [[String]] {
 3         var result = [[String]]()
 4         var currB = Array(repeating:String(Array(repeating:".",count:n)),count:n)
 5     
 6         helper(&result,&currB,n,0)
 7         return result
 8     }
 9     
10     func canPlace( _ row: Int,  _ col: Int, _ board: [String]) -> Bool {
11         var c = -1
12         for i in 0..<row {
13             for j in 0..<board[0].characters.count {
14                 if charAt(board[i], j) == "Q" {
15                     c = j
16                     break
17                 }
18             }
19             
20             // check col
21             if c == col {
22                 return false
23             }
24             
25             // check diagnol
26             if abs(c - col) == abs(i - row) {
27                 return false
28             }
29         }
30         
31         return true
32     }
33     
34     func charAt(_ str: String, _ index: Int) -> Character {
35         return str[str.index(str.startIndex, offsetBy: index)]
36     }
37     
38     
39     func helper(_ result: inout [[String]], _ currB: inout [String], _ n: Int, _ row: Int) {
40     
41         if(row>=n) {
42             var curr = currB
43             result.append(curr)
44             return
45         }
46 
47         for col in 0..<n {
48             if(canPlace(row,col,currB)) {
49                 //print("Placing Q at row:",row,"col:",col)
50                 currB[row] = String(currB[row].prefix(col)) + String("Q") + String(currB[row].dropFirst(col + 1))
51                 helper(&result,&currB,n,row+1)                
52                 //Backtrack
53                 currB[row] = String(currB[row].prefix(col)) + String(".") + String(currB[row].dropFirst(col + 1))
54             }
55             
56         }
57     
58         return 
59     }
60 }