Swift BackTracking N-queen

Question

I am trying to solve the N-queen problem. You can find the problem in https://leetcode.com/problems/n-queens/.

For Backtracking, I have learned that we can solve the problem with three keys:

1. Make Choices

2. Constraints

3. Goal

So I came up with this solution:

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 + "."
                }
            }
        }
    }
}

But it hits time limited. So I am wondering whether my solution is using Backtracking? What goes wrong, How can I improve the solution, How can we Solve the Backtracking problem? What defines Backtracking?

Thanks a lot.

Answer 1

Your solution is backtracking. It backtracks when it can no longer find an available space (chessboard[row][col] == 0) to place a queen. Since it is finding all possible solutions, it also backtracks after it finds a solution and inserts it into the result.

Your solution is merely trying too many trial positions in each call to solve. Note that there can only ever be one queen on any given row. Because of this, solve can work more efficiently by only trying to place queens on a single row in each call to solve. In the first call to solve, try placing the queen on row 0. Then, you'll only be considering n possible placements instead of n * n. On the second call to solve, try placing the queen on row 1. The current row can be computed as n minus the number of queens remaining or n - queens.

With this slight modification, your code runs much faster and successfully passes when submitted to 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)
            }
        }
    }
}