在之前的文章里，我们介绍了图相关的一些算法。今天我们通过N皇后问题来讨论下回溯算法。
首先，我们先介绍下什么是回溯算法：
- 回溯算法可以理解为：通过选择不同的岔路口来通往目的地或者说是得到想要的结果。
在我们之间文章探讨的图的深度优先搜索算法(DFS)和树的中序遍历中，就是典型的回溯应用。
那什么是八皇后问题呢？
-
在 8 * 8格的国际象棋上摆放八个皇后，使其不能互相攻击：任意两个皇后都不能处于同一行，同一列，同一斜线上
EightQueue1.jpeg
为简化问题，我们先分析一下 四皇后 问题。
EightQueue2.png
- 1代表当前格子摆放一个皇后。
- 蓝色格子代表不能在该格子上摆放皇后。
在 4 x 4 方格中，我们先在第一行的第一列摆放一个皇后，那么在第二行第一列和第二行的第二列就不能摆放皇后了。
EightQueue3.png
我们将皇后放在第二行的第三列。接下来，就要在第三行摆放皇后，根据规则，第三行没有合适的位置可以摆放皇后，我们回溯到第二行。
EightQueue4.png
由于之前我们是在第二行的第3列，所以我们这次将皇后安放在第二行的第四列。
EightQueue5.png
第三行只有第二列可以摆放皇后，摆放第三行的皇后后，第4行没有可以摆放皇后的位置了。我们回溯到第3行，由于第3行第3列和第4列不能摆放皇后，我们回溯到第2行，第二行已经摆到第4列了，没有位置可以摆放皇后了，我们回溯到第一行：
EightQueue6.png
我们将第一行的皇后摆放在第2列。
EightQueue7.png
然后开始在第二行的第4列摆放一个皇后。
EightQueue8.png
最后在第4行第3列摆放一个皇后：
EightQueue9.png
通过以上步骤，我们就将4个皇后的位置摆放齐全了，就得到了一种摆放皇后的方式。
实现
我们首先我们先定义一个类
class Queues {
var cols:[Int] // 数组索引是行号，数组元素是列号
var ways: Int = 0 // 一共多少种摆法
init(_ count: Int) {
cols = Array.init(repeating: -1, count: count)
}
}
- cols:数组索引是行号，数组元素是列号。
- ways: 一共多少种摆法。
接下来，我们先写下辅助方法
/*
判断第row行 第 col列是否可以摆放皇后
*/
func isValid( _ row: Int, _ col: Int) -> Bool {
for i in 0..<row {
// 判断第col列有没有摆放皇后
if cols[i] == col {
return false
}
// 第i行的皇后和第row行第col列格子处在同一斜线上
if row - i == abs(col-cols[i]) {
return false
}
}
return true
}
该方法是用来判断第row行 第 col列是否可以摆放皇后
// 摆放第几行
func place(_ row: Int){
if row == cols.count {
ways += 1
return
}
for col in 0..<cols.count {
if isValid(row, col) {
print("row: \(row), col: \(col)")
cols[row] = col
place(row + 1)
}
}
}
如果第row行，第col列可以摆放皇后，我们就将皇后进行摆放，然后，摆放下一行。
func placeQueues(_ n: Int){
if n < 1 {
return
}
cols = Array.init(repeating: -1, count: n)
place(0)
}
最后，完善以上排放方法。
测试
func testEightQueue(){
let queue = Queues(8)
queue.placeQueues(8)
print(queue.ways)
let queue4 = Queues(4)
queue4.placeQueues(4)
print(queue4.ways)
XCTAssert(queue.ways == 92 && queue4.ways == 2)
}
最后附上本文的相关代码DataAndAlgorim
网友评论