## DFS&BFS - 51. N-Queens

Updated on with 0 views and 0 comments
1. N-Queens

The n-queens puzzle is the problem of placing n queens on an n_×_n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where `'Q'` and `'.'` both indicate a queen and an empty space respectively.

Example:

``````Input: 4
Output: [
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
``````

n皇后问题是经典的递归回溯问题，做法就是递归棋盘，一排一排的摆放皇后，然后使用对应列和对角线不能摆放皇后来剪枝。

go：

``````var col, dia1, dia2 []bool

func solveNQueens(n int) [][]string {
var res [][]string

col = make([]bool, n)
dia1 = make([]bool, 2*n-1)
dia2 = make([]bool, 2*n-1)

putQueen(n, 0, []int{}, &res)

return res
}

// 尝试在一个n皇后问题中，摆放第index行的皇后位置
func putQueen(n int, index int, row []int, res *[][]string) {
if index == n {
*res = append(*res, generatedBoard(n, row))
}

for i := 0; i < n; i++ {
if !col[i] && !dia1[index+i] && !dia2[index-i+n-1] { // 对应列、对角线、反对角线没有皇后
row = append(row, i)
col[i] = true
dia1[index+i] = true
dia2[index-i+n-1] = true
// 尝试在index + 1 摆放皇后
putQueen(n, index+1, row, res)
col[i] = false
dia1[index+i] = false
dia2[index-i+n-1] = false
row = row[:len(row)-1]
}
}
}

func generatedBoard(n int, row []int) []string {
var res []string
for i := 0; i < n; i++ {
var temp string
for j := 0; j < n; j++ {
if j == row[i] {
temp = temp + "Q"
} else {
temp = temp + "."
}
}
res = append(res, temp)
}
return res
}
``````