首先提一下八皇后的问题:
在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
代码问题:
用下面我自己的方法实现的八皇后,结果出现了无尽的循环。可能是思路还是哪里的不严谨?请教大伙帮忙改改!我已经尽力了。。。
注:
代码可以直接粘贴复制进xcode的playground进行测试!
class ChessBoard {
var limit: Int
var queens = [Queen]()
init(limit: Int) {
self.limit = limit
}
// 判断该位置是否可以放下皇后
func isSafeForQueen(atRow row: Int, col: Int) -> Bool {
for q in queens {
// 该行中有皇后
if q.row == row { return false }
// 该列中有皇后
if q.col == col { return false }
// 该对角线上有皇后
// 棋盘上两棋子(i,j),(a,b)满足在同一对角线的条件:|i-a| == |j-b|
if abs(q.row-row) == abs(q.col-col) { return false }
}
return true
}
// 递归方法:
func dropQueen(atRow r: Int, c: Int) {
// 进行到最后一行
if r == limit {
if queens.count < 8 {
queens.removeLast()
let q = queens.last!
dropQueen(atRow: q.row, c: q.col+1)
}
output() // 如果成功放置8个皇后,就输出结果
return
}
// 进行到该行最后一列
if c == limit {
queens.removeLast()
let q = queens.last!
// 返回上一行
dropQueen(atRow: r-1, c: q.col+1)
}
// 判断在(r,c)位置是否能放皇后,如果可以,就递归下一行;如果不行,就判断下一个点
if isSafeForQueen(atRow: r, col: c) {
let q = Queen(row: r, col: c)
queens.append(q)
dropQueen(atRow: r+1, c: c)
} else {
dropQueen(atRow: r, c: c+1)
}
}
func play() {
dropQueen(atRow: 0, c: 0) // 从(0,0)开始
}
func output() -> String {
var s = ""
for q in queens {
s += "(\(q.row),\(q.col))"
}
return s
}
}
struct Queen {
var row: Int
var col: Int
}
// 测试:
let b = ChessBoard(limit: 8)
//b.play()