Валидация доски судоку 9x9 с использованием golang и параллелизма - PullRequest
Новая
       8

Валидация доски судоку 9x9 с использованием golang и параллелизма

0 голосов
/ 24 октября 2019

Я практикую golang, делая проблемы с кодированием на LeetCode. Я пытаюсь решить простую головоломку судоку (она только проверяет доску). Нет строк с одинаковыми цифрами, нет столбцов с одинаковыми цифрами, нет блоков 3х3 с одинаковыми цифрами. Я пытаюсь использовать параллелизм для изучения 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 () блокировка для освобождения и код для продвижения вперед. Тогда я ожидаю, что один из результатов в канале будет ложным и вернет ложь, если так. В противном случае, после того, как все элементы в канале пройдены, и ложь не найдена, я ожидал бы True.

1 Ответ

0 голосов
/ 24 октября 2019

Ваши программы не могут позвонить wg.Done(), потому что все они ждут, чтобы добавить свое значение в канал. Но так как вы используете значения из канала только после wg.Wait(), все процедуры, кроме одного, никогда не вызовут wg.Done().

. На самом деле вам не нужна группа WaitGroup, просто удалите ее.

Другие комментарии:

  1. Вы должны переместить defer wg.Done() на первую строку isValidSlice. Вызов defer в последней строке вашей функции не имеет особого смысла.
  2. Вам нужна только группа WaitGroup, если вы хотите правильно закрыть канал, вы можете сделать это в дополнительной процедуре, см. Ниже примеркак это сделать. 
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
}
...