N皇后问题（Go版本）

SyntaxError 发布于 3 月 9 日

题目来源：Leetcode 51题

最近在学习go语言，用go解决了个N皇后问题，这里分享下心得。
N皇后是经典的回溯问题，解决这种问题，都是有特定模板的，这里我写下回溯法的伪代码模板。

def backTrace():
    if 结束条件
        执行相应操作
        return
    for i in 条件:
        做选择
        backTrace()
        撤销选择

然后的话，只需拿模板往上套就行。
我的解题思路是：从上往下往棋盘中一行一行的填充，填充时对应模板中的做选择，即选择在一行中某一列位置填充上Q皇后，然后进入递归，后面紧跟着撤销之前选择的位置。进入递归后，首先是进行位置的判定，即判断上面、左上、右上这几个位置有没有冲突，如果有就立即结束。然后判断是否是最后一行，如果是，那么就将这个结果插入到存储最终结果的切片中。

下面是代码：

import "fmt"

var Res [][]string
var N int


func Recursion(mid []string, i,j int){
    // mid代表存储中间结果的string切片，i代表棋盘的第几行，j代表第几列已经有Q了

    // 对插入的这个位置左上、上、右上进行判断，是否存在皇后
    // 先判断上
    for idx:=i-1;idx>=0;idx--{
        if mid[idx][j] == 'Q'{
            return
        }
    }

    // 再判断左上
    for x,y:=i-1,j-1;x>=0&&y>=0;x,y=x-1,y-1{
        if mid[x][y] == 'Q'{
            return
        }
    }

    // 再判断右上
    for x,y:=i-1,j+1;x>=0&&y<N;x,y=x-1,y+1{
        if mid[x][y] == 'Q'{
            return
        }
    }

    if i==N-1{
        // 遍历过了最后一行，直接结束
        Res = append(Res, mid)
        return
    }


    subMid := make([]byte, 0)
    for idx := 0; idx < N; idx++ {
        subMid = append(subMid, '.')
    }

    for idx:=0;idx<N;idx++{
        subMid[idx] = 'Q'
        length := len(mid)
        Recursion(append(mid[:length:length], string(subMid)), i+1, idx)
        subMid[idx] = '.'
    }
}



func solveNQueens(n int) [][]string {
    N = n
    Res = make([][]string, 0)

    Recursion(make([]string, 0), -1,-1)

    return Res
}



func main() {
    res := solveNQueens(4)
    fmt.Println(res)
}