2 hksx1987 hksx1987 于 2014.12.14 22:11 提问

swift未解决八皇后的问题代码

首先提一下八皇后的问题:
在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()

1个回答

devmiao
devmiao   Ds   Rxr 2014.12.14 23:36
hksx1987
hksx1987 多谢,只可惜看不到他的demo了。。
大约 3 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!