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

Question

我正在通过在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() 锁被释放并且代码继续前进。然后，我希望频道中的结果之一为假，如果是 return 则为假。否则，通道中的所有元素遍历后，没有发现false，我希望是True。

Answer 1

您的 goroutine 无法调用 wg.Done()，因为它们都在等待在通道中添加它们的值。但是由于您只在 wg.Wait() 之后使用通道中的值，所有 goroutines 除了一个永远不会调用 wg.Done().

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

其他评论：

您应该将 defer wg.Done() 移动到 isValidSlice 的第一行。在函数的最后一行调用 defer 没有多大意义。
如果你想正确关闭通道，你只需要一个 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 数独板

Validating 9x9 sudoku board using golang and concurrency

sudoku

go