文章 220
评论 7
浏览 152712
DFS&BFS - 51. N-Queens

DFS&BFS - 51. N-Queens

  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皇后问题是经典的递归回溯问题,做法就是递归棋盘,一排一排的摆放皇后,然后使用对应列和对角线不能摆放皇后来剪枝。
在判断对应列的是否能摆放的时候,因为每行只能摆放一个,所以一个一维数组就能判断某列是否已经摆放过皇后
而对于正对角线,可以很容易算出对于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
}


标题:DFS&BFS - 51. N-Queens
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/09/23/1569250490917.html

Nothing just happens, it's all part of a plan.

取消