Swift BackTracking N-королева

Question

Я пытаюсь решить проблему N-королевы.Вы можете найти проблему в https://leetcode.com/problems/n-queens/.

. Для возврата я узнал, что мы можем решить эту проблему с помощью трех клавиш:

1. Сделать выбор

2. Ограничения

3. Цель

Итак, я пришел к такому решению:

func solveNQueens(_ n: Int) -> [[String]] {

    typealias ChessBoard = [[Int]]
    var result = Set<ChessBoard>()


    func getIndexsOfDiagonal(row:Int,column:Int) -> [(row:Int,col:Int)] {
        var indexs = [(Int,Int)]()

        var rowIndex = row
        var colIndex = column

        while rowIndex < n && colIndex < n {
            indexs.append((rowIndex,colIndex))
            rowIndex += 1
            colIndex += 1
        }

        rowIndex = row
        colIndex = column

        while rowIndex >= 0 && colIndex >= 0  {
            indexs.append((rowIndex,colIndex))
            rowIndex -= 1
            colIndex -= 1
        }

        rowIndex = row
        colIndex = column

        while rowIndex >= 0 && colIndex < n {
            indexs.append((rowIndex,colIndex))
            rowIndex -= 1
            colIndex += 1
        }

        rowIndex = row
        colIndex = column

        while rowIndex < n && colIndex >= 0 {
            indexs.append((rowIndex,colIndex))
            rowIndex += 1
            colIndex -= 1
        }
        return indexs
    }

    func placeQuees(chessboard:ChessBoard,row:Int,column:Int) ->ChessBoard {
        var newChessBorad = chessboard
        //set row
        for index in 0..<n {
            newChessBorad[row][index] = -1
        }
        //set column
        for index in 0..<n {
            newChessBorad[index][column] = -1
        }
        //set diagonal
        for index in getIndexsOfDiagonal(row:row,column:column) {
            newChessBorad[index.row][index.col] = -1
        }

        newChessBorad[row][column] = 1

        return newChessBorad
    }

    func solve(chessboard:ChessBoard, queens: Int) {

        if queens == 0 {
            //Goal
            result.insert(chessboard)
        }

        for row in 0..<n {
            for col in 0..<n {
                //Choices
                if chessboard[row][col] == 0 {
                    //Constraints
                    let new = placeQuees(chessboard: chessboard, row: row, column: col)
                    solve(chessboard: new, queens: queens - 1)
                }
            }
        }
    }

    solve(chessboard: Array(repeating: Array(repeating: 0, count: n), count: n), queens: n)


    return result.map {
        //chessboard
        $0.map {
            //row to string
            $0.reduce("") { string,value in
                if value == 1 {
                    return string + "Q"
                } else {
                    return string + "."
                }
            }
        }
    }
}

Но это ударяет по времени.Поэтому мне интересно, использует ли мое решение Backtracking?Что идет не так, как я могу улучшить решение, как мы можем решить проблему с возвратом?Что определяет Backtracking?

Большое спасибо.

Answer 1

Ваше решение возвращается. Он возвращается, когда больше не может найти доступное пространство (chessboard[row][col] == 0) для размещения королевы. Так как он находит все возможные решения, он также возвращается после того, как находит решение и вставляет его в result.

Ваше решение - просто пробовать слишком много пробных позиций в каждом вызове на solve. Обратите внимание, что в любой строке может быть только одна королева. Из-за этого solve может работать более эффективно, только пытаясь поместить ферзей в одну строку в каждом вызове solve. При первом вызове solve попробуйте поставить королеву на row 0. Тогда вы будете рассматривать только n возможных мест размещения вместо n * n. При втором вызове solve попробуйте поставить королеву на row 1. Текущий row может быть вычислен как n минус количество оставшихся королев или n - queens.

С этой небольшой модификацией ваш код работает намного быстрее и успешно проходит при отправке в LeetCode:

func solve(chessboard:ChessBoard, queens: Int) {

    if queens == 0 {
        //Goal
        result.insert(chessboard)
    }
    else {
        let row = n - queens
        for col in 0..<n {
            //Choices
            if chessboard[row][col] == 0 {
                //Constraints
                let new = placeQuees(chessboard: chessboard, row: row, column: col)
                solve(chessboard: new, queens: queens - 1)
            }
        }
    }
}