前言
最近在用Go并發(fā)實現(xiàn)n皇后問題中遇到很多的坑础倍，在此進行記錄擎宝。
n后問題以及單線程實現(xiàn)
n后問題：簡單來說就是在n*n的棋盤上放置n個皇后翘地，使每兩者之間都不在同一行，同一列拦惋，同一斜線上。求滿足條件的解的個數(shù)安寺？
// array[i] 代表第 i 行n皇后放置位置為第 arry[i] 列厕妖，index代表當前要放置皇后的行號
type Process struct {
array []int
index int
}
// 檢查該行放置后會不會沖突
func check(process Process) bool {
array := process.array
k := process.index
for i := 0; i < k; i++ {
if array[i] == array[k] {
return true
}
if int(math.Abs(float64(array[k]-array[i]))) == k-i {
return true
}
}
return false
}
func NQueen(process Process, n int) int {
if process.index >= n {
return 1
}
res := 0
for j := 0; j < n; j++ {
process.array = append(process.array, j)
if check(process) == false {
process.index++
res += NQueen(process, n)
process.index--
}
process.array = process.array[:len(process.array)-1]
}
return res
}
func Provide(n int) int {
process := Process{
array: make([]int, 0),
index: 0,
}
return NQueen(process, n)
}
func main() {
fmt.Println(Provide(12))
}
錯誤的并發(fā)代碼
思路：創(chuàng)建協(xié)程去執(zhí)行 NQueen 函數(shù)，并將結(jié)果放入 channel挑庶，最后累加得到最終結(jié)果言秸。于是，代碼可能是下面這個樣子的：
// 其他函數(shù)不變
func NQueen(ch chan int, process Process, n int) {
if process.index >= n {
ch <- 1
return
}
count := 0
newch := make(chan int, n)
for j := 0; j < n; j++ {
process.array = append(process.array, j)
if check(process) == false {
process.index++
count++
go NQueen(newch, process, n)
process.index--
}
process.array = process.array[:len(process.array)-1]
}
res := 0
for i := 0; i < count; i++ {
res += <-newch
}
ch <- res
}
func Provide(n int) int {
process := Process{
array: make([]int, 0),
index: 0,
}
ch := make(chan int, 1)
NQueen(ch, process, n)
return <-ch
}
這樣迎捺，你可能發(fā)現(xiàn)举畸，答案并不是我們預期的那樣。
分析：
（1）這里只傳入同一個 process 實例凳枝，那么多個協(xié)程同時對他們操作抄沮，不加以控制的話，肯定會出現(xiàn)問題岖瑰；所以我們給每個協(xié)程一份單獨的 process 實例叛买。
（2）第二個，我們著重來講 process.array = append(process.array, j) 問題蹋订。
append函數(shù)機制
首先明確我們的需求：重新開辟內(nèi)存空間率挣，值為原來數(shù)組切片基礎(chǔ)上，增加一個元素
append機制：
當切片還有可用容量露戒，調(diào)用append椒功，會將值直接加到切片中捶箱，這時原切片和現(xiàn)切片共用底層數(shù)組，所以地址相同蛾茉。
而當容量不足讼呢，系統(tǒng)會重新開辟一塊兒內(nèi)存，所以原切片和現(xiàn)切片底層數(shù)組不同谦炬。
func main() {
ch := make([]int, 5)
ch = append(ch, 1, 2, 3, 4)
fmt.Printf("%p\n", ch)
aa := append(ch, 5)
fmt.Printf("%p\n", aa)
bb := append(ch, 5, 6)
fmt.Printf("%p\n", bb)
}
所以悦屏，我們每次初始化新的切片，使系統(tǒng)分配不同的內(nèi)存空間键思。
代碼實現(xiàn)
type Process struct {
array []int
index int
}
func check(process Process) bool {
array := process.array
k := process.index - 1
for i := 0; i < k; i++ {
if array[i] == array[k] {
return true
}
if int(math.Abs(float64(array[k]-array[i]))) == k-i {
return true
}
}
return false
}
func NQueen(ch chan int, process Process, n int) {
if process.index >= n {
ch <- 1
return
}
count := 0
newch := make(chan int, n)
for j := 0; j < n; j++ {
newProcess := Process{
array: make([]int, 0),
index: process.index + 1,
}
newProcess.array = append(newProcess.array, process.array...)
newProcess.array = append(newProcess.array, j)
if check(newProcess) == false {
count++
go NQueen(newch, newProcess, n)
}
}
res := 0
for i := 0; i < count; i++ {
res += <-newch
}
ch <- res
}
func Provide(n int) int {
process := Process{
array: make([]int, 0),
index: 0,
}
ch := make(chan int, 1)
NQueen(ch, process, n)
return <-ch
}
func main() {
fmt.Println(Provide(8))
}
如何限流
何為限流础爬，就是同一時刻創(chuàng)建恒定個協(xié)程。這里我們用channel來進行限流吼鳞。
type Process struct {
array []int
index int
}
func check(process Process) bool {
array := process.array
k := process.index - 1
for i := 0; i < k; i++ {
if array[i] == array[k] {
return true
}
if int(math.Abs(float64(array[k]-array[i]))) == k-i {
return true
}
}
return false
}
var channel = make(chan int, 5)
func NQueen(ch chan int, process Process, n int) {
<-channel
if process.index >= n {
ch <- 1
return
}
count := 0
newch := make(chan int, n)
for j := 0; j < n; j++ {
newProcess := Process{
array: make([]int, 0),
index: process.index + 1,
}
newProcess.array = append(newProcess.array, process.array...)
newProcess.array = append(newProcess.array, j)
if check(newProcess) == false {
channel <- 1
count++
go NQueen(newch, newProcess, n)
}
}
res := 0
for i := 0; i < count; i++ {
res += <-newch
}
ch <- res
}
func Provide(n int) int {
process := Process{
array: make([]int, 0),
index: 0,
}
ch := make(chan int, 1)
channel <- 1
NQueen(ch, process, n)
return <-ch
}
func main() {
fmt.Println(Provide(8))
}
