swift - 这是我解决八皇后难题的快速代码

Question

八皇后难题是将八个国际象棋皇后放置在一个8×8的棋盘上，使两个皇后之间不会相互威胁的问题。因此，解决方案要求没有两个皇后共享相同的行、列或对角线。八皇后难题是更一般的 n 皇后问题的一个例子，即在 n×n 棋盘上放置 n 个皇后，其中除了 n=​​2 或 n=3 之外的所有自然数 n 都存在解。

但是，有没有人可以帮我解决这个在递归方法中无限循环的问题？

ps:你可以直接复制/粘贴到playground试试，谢谢!

class ChessBoard {

    var limit: Int
    var queens = [Queen]()

    init(limit: Int) {
        self.limit = limit
    }

    // Check if (i,j) is a safe position for queen
    func isSafeForQueen(atRow row: Int, col: Int) -> Bool {

        for q in queens {
            // not in same row
            if q.row == row { return false }
            // not in same column
            if q.col == col { return false }
            // not in same diagol line
            if abs(q.row-row) == abs(q.col-col) { return false }
        }

        return true
    }

    // recursive method
    func dropQueen(atRow r: Int, c: Int) {

        // running into last row
        if r == limit {
            if queens.count < 8 {
                queens.removeLast()
                let q = queens.last!
                dropQueen(atRow: q.row, c: q.col+1)
            }
            output() // if success, log out the positions
            return
        }
        // running into last column of current row
        if c == limit {
            queens.removeLast()
            let q = queens.last!
            // if no position for queen at current row, then back to last row
            dropQueen(atRow: r-1, c: q.col+1)
        }
        // if this postion is safe for queen, then drop the queen and try next row; if not, try next spot
        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) // game will start at(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
}

// Tesing：
let b = ChessBoard(limit: 8)
//b.play()

Answer 1

看来您在理解递归的概念时遇到了困难。递归并不意味着一切 都变成递归调用。在函数 dropQueen 中，您正在使用递归调用，就像它们是 goto 一样。

尤其是这个:

dropQueen(atRow: r-1, c: q.col+1)

这显然是一种回溯的尝试。下定决心；要么做回溯要么使用递归!在递归中，回到先前的决定是一个return。如有必要，返回一个 bool 值让调用者知道递归调用是否找到了解决方案 (return true) 或没有 (return false)。如果您希望您的程序找到所有 可能的解决方案，而不仅仅是第一个，则不需要它。

另一个引起我注意的电话:

dropQueen(atRow: r, c: c+1)

递归调用在这里有点矫枉过正，而且令人困惑；使用循环扫描所有可能的列。顺便说一句，通过进行此更改，您会发现整个第二个函数参数变得多余。

这只给我们留下了一个回溯调用；这绰绰有余。

dropQueen(atRow: r+1, c: c)

正如 vacawama 所指出的，第二个参数 c: c 似乎是错误的。当您前进一行 (r+1) 时，为什么要排除您放在棋盘上的最后一个皇后左边的所有内容？

如果你想做递归，那么想想你的递归函数应该做什么。通常，您希望它在已经被 r 个皇后占据的棋盘上放置 (8-r) 个皇后。您正在逐行工作，因此在您的方法中 r 只是当前行号。想一想如何根据第 r+1 行的解决方案来表达第 r 行问题的解决方案。为最后一行做一个特殊的异常(exception)；一旦 r 等于极限，解决方案就很简单(需要放置零皇后)；你完成了。

哦，请重命名函数 dropQueen；该名称清楚地表明您正在以错误的心态从事此工作。到现在为止，您应该能够想出更合适的东西。

---

编辑:您为完成这项工作付出了相当大的努力，因此我将与您分享我的解决方案。它使用您的原始代码(如您的问题所示)，但函数 dropQueen 完全重写(并且少了一个参数)。请注意它是多么简短；这是典型的递归。

func dropQueen(atRow r: Int) {
    if queens.count < limit {
        for col in 0...limit-1 {
            if isSafeForQueen(atRow: r, col: col) {
                let q = Queen(row: r, col: col)
                queens.append(q)
                dropQueen(atRow: r+1)
                if queens.count == limit {
                    return
                }
                queens.removeLast()
            }
        }
    }
}

作为奖励，如果将 return 替换为 println(output())，则程序将打印所有 92 个解决方案。您可以在以下位置查看实际效果: http://swiftstub.com/923601919/