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. palindromic

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相同, 使用递归遍历每一行所有位置,判断该位置是否合法,不合法返回,合法则进入下一行。

好像大家给这种方法取了一个很洋气的名字叫回溯

在国际象棋中,皇后可以攻击直线和斜线上的目标

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
}