问题描述

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

首先提一下八皇后的问题：
在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

代码问题：
用下面我自己的方法实现的八皇后，结果出现了无尽的循环。可能是思路还是哪里的不严谨？请教大伙帮忙改改！我已经尽力了。。。

注：
代码可以直接粘贴复制进xcode的playground进行测试！

class ChessBoard {

var limit: Intvar 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 }        // 该对角线上有皇后        // 棋盘上两棋子(ij)(ab)满足在同一对角线的条件：|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)    }    // 判断在(rc)位置是否能放皇后，如果可以，就递归下一行；如果不行，就判断下一个点    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) // 从(00)开始}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()

解决方案

这里有个objective-c版的eight queens，可以参考
http://ijoshsmith.com/2012/04/22/objective-c-genetic-algorithm-that-solves-the-8-queens-puzzle/