39_回溯思想

文章目录
  1. 1. 回溯思想

记录回溯思想

回溯思想

遇到分岔路口时, 随意选择一条路,当发现一条路不通时,回到上一个岔路口。

八皇后问题:

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
54
55
56
57
58
59
60
61
62
class Queen8 {
var count = 0

var result = Array(repeating: 0, count: 8)
func cal8Queens(row:Int) {
if row == 8 {
printQueens(result: result)
return
}

for column in 0..<8 { //每一行都有8种方法
if isOK(row: row, column: column) {
result[row] = column
cal8Queens(row: row + 1)
}
}
}

func isOK(row: Int, column: Int) -> Bool {
var leftUp = column - 1
var rightUp = column + 1
for i in stride(from: row-1, through: 0, by: -1) {
if result[i] == column {
return false
}

if leftUp >= 0 && result[i] == leftUp {
return false
}

if rightUp < 8 && result[i] == rightUp {
return false
}

leftUp -= 1
rightUp += 1
}
return true
}

func printQueens(result: [Int]) {
for i in 0..<8 {
for j in 0..<8 {
if result[i] == j {
print("Q ", terminator: "")
} else {
print("* ", terminator: "")
}
}
print(" ")
}
print("一种方案完成---------")
count += 1
}

static func testQueen8() {
let queen = Queen8()

queen.cal8Queens(row: 0)
print(queen.count) //92种方案
}
}