ac solution code


  • 0

    Explanation

    Check possible columns row by row based on DFS:
    1. If satisfy the below 2 conditions, then ignore it

    1). the column is already used 
    or
    2). the column is on 45° /135°  diagonals with the placed queens
    

    2. Otherwise, place a queen on it and keep DFS procedure.

    DFS. time = (n^4); space = O(n^2)

    func solveNQueens(_ n: Int) -> [[String]] {
            var res = [[String]]()
            var usedCols = [Int](repeating: -1, count: n)// usedCols[i]: Column of the queen in row i
            DFS(&usedCols, &res, 0)
            return res
        }
        private func DFS(_ usedCols: inout [Int], _ res: inout [[String]], _ row: Int) {
            let n = usedCols.count
            if row == n {// Termination case
                res.append(drawGrids(usedCols))
                return
            }
            // Check Possible columns for the inputed row
            for col in 0 ..< n {
                if isValid(usedCols, row, col) {
                    usedCols[row] = col
                    DFS(&usedCols, &res, row + 1)// Move on to the next row
                }
            }
        }
        // Check if the column is valid to place queen for the row.
        private func isValid(_ usedCols: [Int], _ row: Int, _ col: Int) -> Bool {
            for i in 0 ..< row {
                // Excludes used columns and diagonal positions
                // (x2-x1)/(y2-y1) == 1 or -1
                if usedCols[i] == col || row - i == abs(col - usedCols[i]) {
                    return false
                }
            }
            return true
        }
        private func drawGrids(_ usedCols: [Int]) -> [String]{
            var res = [String]()
            for i in usedCols {
                var line = [Character](repeating: ".", count: usedCols.count)
                line[i] = "Q"
                res.append(String(line))
            }
            return res
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.