ios - Swift 中 nxn 棋盘实现的递归 n 皇后区

Question

我正在尝试创建一个递归的 Swift 实现来解决经典难题:“我们如何在 n × n 的国际象棋网格上分配 n 个皇后，以便没有皇后可以威胁另一个”。

使用现有代码我遇到了以下问题:

1. 代码不会生成 n<=8 的所有解决方案
2. 代码不会为 n>=9 产生任何解决方案

3. 似乎无法比较 n=8 (8x8) 和更大的解决方案，因为我通过移动代表皇后或空磁贴:

   public override var hash: Int {
       var hash = 0
       for i in 0...self.board.count-1 {
           for j in 0...self.board.count-1 {
               if self.board[i][j].state == .Queen {
                   hash |= 1
                   hash <<= 1
               } else {
                   hash <<= 1
               }
           }
   
       }
       return hash
   
   }
   

当电路板大于 8x8 时，值会损坏，因为它大于 64 位(swift Int 是 Int64)。什么是好的解决方案？

我当前的代码:

import UIKit

public typealias Board = Array<Array<Cell>>

@objc protocol QueenPlacementDelegate : class {
    func solutionsFound(numOfSolutions : Int)
}

class QueenPlacement: NSObject {
    var boardView : TTTBoardView?
    var boardSize : Int = 0
    var solutions : Set<Solution>?
    weak var delegate : QueenPlacementDelegate? 
    private var startCondX : Int = 0
    private var startCondY : Int = 0


    func start() {

        if boardSize == 0 {
            print("Board size was not initialized")
            return
        }

        self.solutions = Set<Solution>()
        var done = false
        self.startCondX = 0; self.startCondY = 0;

        while (!done) {
            let solution = Solution(boardSize: self.boardSize)
            let board = solution.board
            self.placeQueen(startCondX, yLoc: startCondY, board: board)
            let solutionBoard = self.findSolutionForBoard(board)

            if self.numOfQueensOnBoard(solutionBoard) == self.boardSize {
                print("solution found")
                solution.board = solutionBoard
                self.solutions!.insert(solution)
            }

            done = self.advanceStartConditionsAndCheckIfDone()
            if (done) {
                if self.solutions!.count > 0 {
                    self.delegate!.solutionsFound(self.solutions!.count)
                }
            }

        }
    }

    func advanceStartConditionsAndCheckIfDone() -> Bool {
        startCondX++
        if startCondX >= self.boardSize {
            startCondX = 0
            startCondY++
            if startCondY >= self.boardSize {
                return true
            }
        }
        return false
    }


    func placeQueen(xLoc : Int, yLoc : Int, board : Board) {
        board[xLoc][yLoc].state = .Queen
    }

    func findSolutionForBoard(board : Board) -> Board
    {
        let queensPlaced = self.numOfQueensOnBoard(board)
        if queensPlaced == self.boardSize {
            return board
        }
        else
        {
            for i in 0...self.boardSize-1 {
                for j in 0...self.boardSize-1 {
                    if self.canPlaceQueen(xLoc: i, yLoc: j, board: board) {
                        self.placeQueen(i, yLoc: j, board: board)
                    }
                }
            }
            let newQueensPlaced = self.numOfQueensOnBoard(board)

            // recursion exit conditions: could not place any new queen
            if newQueensPlaced > queensPlaced {
                self.findSolutionForBoard(board)
            } else {
                return board
            }
        }

        return board
    }

    func numOfQueensOnBoard(board : Board) -> Int {
        var queensPlaced = 0
        for i in 0...self.boardSize-1 {
            for j in 0...self.boardSize-1 {
                if board[i][j].state == .Queen {
                    queensPlaced++
                }
            }
        }
        return queensPlaced
    }


    func canPlaceQueen(xLoc xLoc : Int, yLoc : Int, board: Board) -> Bool {
        for i in 0...self.boardSize-1 {
            if board[i][yLoc].state == .Queen {
                return false;
            }
            if board[xLoc][i].state == .Queen {
                return false;
            }

        }

        var x : Int
        var y : Int
        x = xLoc; y = yLoc;
        while ++x < self.boardSize && ++y < self.boardSize {
            if board[x][y].state == .Queen {
                return false
            }
        }

        x = xLoc; y = yLoc;
        while --x >= 0 && ++y < self.boardSize {
            if board[x][y].state == .Queen {
                return false
            }
        }

        x = xLoc; y = yLoc;
        while ++x < self.boardSize && --y >= 0 {
            if board[x][y].state == .Queen {
                return false
            }
        }
        x = xLoc; y = yLoc;
        while --x >= 0 && --y >= 0 {
            if board[x][y].state == .Queen {
                return false
            }
        }

        return true

    }


    // singleton!
    static let sharedInstance = QueenPlacement()
    private override init() {}


}

这里有什么问题吗？

附言为了便于阅读 - 可以找到完整的代码库 here

Answer 1

这不是我不知道你的版本有什么问题的答案，但这是另一个(看起来像我测试的那样工作)，有点简单(基于 Scala By Example - The N 皇后问题)。

func queens(n: Int) -> [[Int]] {

    guard n > 3 else {
        return [[Int]]()
    }

    func placeQueens(k: Int) -> [[Int]] {

        guard k > 0 else {
            return [[-1]] //stupid hack to let the app go to the for-loop in the * marked place
        }
        var res = [[Int]]()

        for var q in placeQueens(k - 1) { //* marked place

            if let first = q.first where first == -1 { //this is for removing the hacky -1
                q.removeAll()
            }

            for column in 1...n {

                if isSafe(column, queens: q) {
                    var solution = q
                    solution.append(column)
                    res.append(solution)
                }
            }
        }
        return res
    }
    return placeQueens(n)
}

func isSafe(column: Int, queens: [Int]) -> Bool {

    for (index, q) in queens.enumerate() {
        let dy = (index + 1) - (queens.count + 1)
        let dx = q - column
        let isDiagonal = dy * dy == dx * dx

        if q == column || isDiagonal {
            return false
        }
    }
    return true
}

如果您想得出解决方案:

func drawTable(table: [Int]) -> String {
    var res = ""

    table.forEach {

        for column in 1...table.count {

            if $0 == column {
                res += "X "
            } else {
                res += ". "
            }
        }
        res += "\n"
    }
    return res
}

和

queens(4).forEach {
    print(drawTable($0))
}

计算 n = 13 的 73712 个解决方案需要几分钟时间，超过此时间您可能会用这种方式耗尽内存。