DFS&BFS - 51. N-Queens

51. 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皇后问题是经典的递归回溯问题，做法就是递归棋盘，一排一排的摆放皇后，然后使用对应列和对角线不能摆放皇后来剪枝。
在判断对应列的是否能摆放的时候，因为每行只能摆放一个，所以一个一维数组就能判断某列是否已经摆放过皇后。
而对于正对角线，可以很容易算出对于n*n的棋盘，一共有 2n-1 条对角线，并且对角线的斜率相同，只是对应的偏移量不同，对于这 2n-1 条对角线就可以用一个一维数组来表示，每一位数代表了该对角线，具体来说：对于点[x, y], 是满足 x - y = b，因为x和y的取值范围是[0, n-1],所以，b的取值范围就是【-n+1, n-1】，如果用一维数组来表示 这2n-1 条对角线，那么则是以0为起始点，那么取值范围就是【0，2n-2】，等号左右两边都加上(n-1)，就等于 x - y + (n - 1)。
同理反对角线的方程表达式是 x + y = - b，因为x和y的取值范围是[0, n-1], 所以b的取值范围就是【0, 2n-2】。直接就能用一个一维数组表示。

代码：

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
}