ac solution code

• 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
}
``````

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