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.."]
]
``````

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