Parallel traveling salesman problem solver finishes prematurely

Question

Good time of the day. I'm doing an assignment which involves writing a program that solves Traveling Salesman Problem in parallel using brute-force method. I managed to write a working version but it was a lot slower than consequential version due to numerous memory allocations at a high rate which I attempted to limit as in a code bellow using buffered channel.

SO probably won't allow to fit all the code into post so, please view definition and methods of data structures on Github: https://github.com/telephrag/tsp_go

This version doesn't work at all.

• At the end t will contain empty path and maximum value of uint64 for traveled distance which is set at the beginning.
• As could be seen through debugger, salesman with id of 1 is getting node added to its path at sm.Path[1], but once <-t.RouteQueue occurs in the same call to travel() the program stops despite numerous goroutines are supposedly waiting to write to t.RouteQueue at the moment. It's also confirmed through debugger as well that the program never reaches if-block responsible for setting new shortest path in t.
• If we create sync.Waitgroup for each for-loop the program will crash on deadlock.
• sync.WaitGroup but remove everything related to channel the program would work but do so very slowly. You can get this version at the first commit to main branch of repository above.

Why does the program ends prematurely?

package tsp

func (t *Tsp) Solve() {
    sm := NewSalesman(t)
    sm.Visit(0) // sets bit corresponding to given node in bitmask

    for nextNode := range graph[0] {
        t.RouteQueue <- true // book slot in route queue (buffered channel)
        go t.travel(sm.Copy(t), nextNode)
    }
}

func (t *Tsp) travel(sm *Salesman, node uint64) {
    sm.Distance += graph[sm.TailNode()][node] // increase traveled distance
    if sm.Distance > t.MinDist {              // terminate if traveled distance is bigger than current minimal
        <-t.RouteQueue
        return
    }

    sm.Visit(node)
    sm.Count++               // increase amount of nodes traveled
    sm.Path[sm.Count] = node // add node to path

    if sm.Count == t.NodeCount-1 { // stop if t.NodeCount - 1 nodes traveled
        sm.Count++
        sm.Distance += graph[node][0] // return to zero-node

        t.Mu.Lock()
        if t.MinDist > sm.Distance { // set new min distance and path if they are shorter
            t.MinPath = sm.Path
            t.MinDist = sm.Distance
        }
        t.Mu.Unlock()
    }

    <-t.RouteQueue // free the slot for routes

    for nextNode := range graph[node] {
        if !sm.HasVisited(node) {
            t.RouteQueue <- true
            go t.travel(sm.Copy(t), nextNode)
        }
    }
}