使用 golang 和并发验证 9x9 数独板

从现在开始，努力学习吧！本文《使用 golang 和并发验证 9x9 数独板》主要讲解了等等相关知识点，我会在golang学习网中持续更新相关的系列文章，欢迎大家关注并积极留言建议。下面就先一起来看一下本篇正文内容吧，希望能帮到你！

我正在通过在 leetcode 上做编码问题来练习 golang。我正在尝试解决一个简单的数独难题（它只是验证棋盘）。没有行具有相同的数字，没有列具有相同的数字，没有 3x3 块具有相同的数字。我正在尝试使用并发来学习 go routines/channels/etc...

我无法让等待组完成

import (
    "sync"
    "fmt"
)
func isValidSlice(slice []byte, results chan<- bool, wg *sync.WaitGroup) {
    fmt.Println(slice)
    seen := make(map[byte]bool)
    for _,val := range(slice) {
        if seen[val] {
            if val != '.'{
                results <- false
                defer wg.Done()
                return    
            }
        } else {
            seen[val] = true
        }
    }

    results <- true
    defer wg.Done()
}

func isValidSudoku(board [][]byte) bool {
    // Channel to receive solution
    c := make(chan bool)

    // Number of routines that will run (9 for rows, 9 for cols, 9 for 3x3 blocks)
    var wg sync.WaitGroup

    // Check every row
    for x:= 0; x < 9; x++{
        wg.Add(1)
        go isValidSlice(append([]byte{}, board[x]...), c, &wg)
    }
    for y:= 0; y < 9; y++{
        wg.Add(1)
        go isValidSlice(append([]byte{}, board[0:9][y]...), c, &wg)   
    }
    // Check every 3x3 block
    for x:= 0; x <= 6; x += 3{
        for y := 0; y <= 6; y += 3{
            block_digits := append([]byte{}, board[x][y:y+3]...)
            block_digits = append(block_digits, board[x+1][y:y+3]...)
            block_digits = append(block_digits, board[x+2][y:y+3]...)
            wg.Add(1)
            go isValidSlice(block_digits, c, &wg)
        }
    }

    fmt.Println("got here")
    wg.Wait()
    fmt.Println("never got here")

    for result := range c{
        if !result{
            return false
        }
    }

    return true
}

我期待 wg.wait() 锁释放并且代码继续前进。然后我期望通道中的结果之一为 false，如果是则返回 false。否则，在遍历通道中的所有元素并且没有发现 false 后，我会期望 true。

解决方案

你的 goroutine 无法调用 wg.done() 因为它们都在等待在通道中添加它们的值。但由于您只在 wg.wait() 之后使用通道中的值，因此除一个之外的所有 goroutine 都永远无法调用 wg.done()。

您实际上不需要 waitgroup，只需将其删除即可。

其他评论：

1. 您应该将 defer wg.done() 移至 isvalidslice 的第一行。在函数的最后一行调用 defer 没有多大意义。
2. 如果你想正确关闭通道，你只需要一个 waitgroup，你可以在一个额外的 goroutine 中做到这一点，请参阅下面的示例来了解如何做到这一点。

func isValidSudoku(board [][]byte) bool {

    // ...

    fmt.Println("got here")
    go func(){
        wg.Wait()
        close(c)
    }()
    fmt.Println("never got here")

    for result := range c{
        if !result{
            go func(){
                for _ := range c {
                }
            }()        
            return false
        }
    }
    return true
}

本篇关于《使用 golang 和并发验证 9x9 数独板》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！