LeetCode 51. N-Queens
Description
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.
For example, There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 “…Q”, “Q…”, “..Q."],
[”..Q.", // Solution 2 “Q…”, “…Q”, “.Q.."] ]
这是我第一次做八皇后问题，之前只是听说这么一个名字。
思路与之前[Sudoku-Solver](http://www.orztu.com/leetcode/Sudoku-Solver/)相同，
使用递归遍历每一行所有位置，判断该位置是否合法，不合法返回，合法则进入下一行。
好像大家给这种方法取了一个很洋气的名字叫*回溯*
<small>*在国际象棋中，皇后可以攻击直线和斜线上的目标*</samll>
## Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
func solveNQueens(n int) [][]string {
answer := make([][]string, 0)
board := make([]int, n)
solve(&answer, board, n, 0)
return answer
}
// put a queen on board at line l
func solve(answer *[][]string, board []int, n, l int) {
if n == l {
*answer = append(*answer, convertBoard(board, n))
return
}
for i := 0; i < n; i++ {
if !canBeAttack(board, n, l, i) {
// mark the queen's postion
board[l] = i
solve(answer, board, n, l+1)
}
}
}
// 判断会否被其他皇后攻击
func canBeAttack(board []int, n, x, y int) bool {
for row := 0; row < x; row++ {
col := board[row]
if col == y || abs(row-x) == abs(col-y) {
return true
}
}
return false
}
// 转换成返回格式
func convertBoard(board []int, n int) []string {
ans := make([]string, n)
for i := 0; i < n; i++ {
line := []byte(strings.Repeat(".", n))
line[board[i]] = 'Q'
ans[i] = string(line)
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
