并发实现n皇后问题

前言

最近在用Go并发实现n皇后问题中遇到很多的坑，在此进行记录。

n后问题以及单线程实现

n后问题：简单来说就是在n*n的棋盘上放置n个皇后，使每两者之间都不在同一行，同一列，同一斜线上。求满足条件的解的个数？

// 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))
}

错误的并发代码

思路：创建协程去执行 NQueen 函数，并将结果放入 channel，最后累加得到最终结果。于是，代码可能是下面这个样子的：

// 其他函数不变
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
}

这样，你可能发现，答案并不是我们预期的那样。
分析：
（1）这里只传入同一个 process 实例，那么多个协程同时对他们操作，不加以控制的话，肯定会出现问题；所以我们给每个协程一份单独的 process 实例。
（2）第二个，我们着重来讲 process.array = append(process.array, j) 问题。

append函数机制

首先明确我们的需求：重新开辟内存空间，值为原来数组切片基础上，增加一个元素
append机制：
当切片还有可用容量，调用append，会将值直接加到切片中，这时原切片和现切片共用底层数组，所以地址相同。
而当容量不足，系统会重新开辟一块儿内存，所以原切片和现切片底层数组不同。

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)
}

所以，我们每次初始化新的切片，使系统分配不同的内存空间。

代码实现

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))
}

如何限流

何为限流，就是同一时刻创建恒定个协程。这里我们用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))
}