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

Question

我正在通过在 LeetCode 上做编码问题来练习 golang。我正在尝试解决一个简单的数独难题(它只是验证板)。没有相同数字的行，没有相同数字的列，没有相同数字的 3x3 block 。我正在尝试使用并发来学习 Go Routines/Channels/Etc...

我无法让 WaitGroup 完成

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() 锁释放和代码继续前进。然后我期望 channel 中的结果之一为假，如果是，则返回假。否则，在 channel 中的所有元素都被遍历并且没有找到 false 之后，我会期待一个 True。

Answer 1

你的 goroutine 不能调用 wg.Done()因为他们都在等待在 channel 中增加他们的值(value)。但是由于您只在 wg.Wait() 之后使用 channel 中的值, 除了一个之外的所有 goroutine 都不会调用 wg.Done() .

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

其他的建议:

你应该移动 defer wg.Done()到 isValidSlice 的第一行.在函数的最后一行调用 defer 没有多大意义。

如果你想正确地关闭 channel ，你只需要一个 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
}