关于golang:N皇后问题Go版本

41次阅读

共计 1075 个字符,预计需要花费 3 分钟才能阅读完成。

题目起源: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)
}

正文完
 0