Solution to the n queen problem in go using genetic algorithms. Includes a solution with and without using goroutines

n-queens.go

package main

import (
    "fmt"
	"math/rand"
    "time"
)

type Individual struct {
    queens []int
    generation int
    fitness int
}

type Population []*Individual
type IndividualSlice Population

func NewIndividual(queens []int, generation int) Individual {
    fitness := computeFitness(queens)

    return Individual{queens, generation, fitness}
}

func computeFitness(queens []int) int {
    n := len(queens)
    fDiags := make([]bool, len(queens) * 2 - 1)
    bDiags := make([]bool, len(queens) * 2 - 1)
    rows := make([]bool, len(queens))

    var attacks int

    for x, y := range queens {
        f := y + n - x - 1
        b := n * 2 - x - y - 2

        if fDiags[f] {
            attacks++
        } else {
            fDiags[f] = true
        }

        if bDiags[b] {
            attacks++
        } else {
            bDiags[b] = true
        }

        if rows[y] {
            attacks++
        } else {
            rows[y] = true
        }
    }

    return attacks
}

func createRandomIndividual(n int) Individual {
    var queens []int

    for i := 0; i < n; i++ {
        queen :=  i
        queens = append(queens, queen)
    }

    for i := n - 1; i > 0; i-- {
        j := rand.Int() % (i + 1)
        queens[i], queens[j] = queens[j], queens[i]
    }

    return NewIndividual(queens, 0)
}

func (ind Individual) Mutate() Individual {
    n := len(ind.queens)

    newQueens := make([]int, n)
    copy(newQueens, ind.queens)

    i := rand.Intn(n)

    newQueens[i] = rand.Intn(n)

    return NewIndividual(newQueens, ind.generation + 1)
}

func (ind Individual) Crossover(other Individual) (Individual, Individual) {
    n := len(ind.queens)
    i := rand.Intn(n - 1)

    newGen := ind.generation + 1

    newQ1 := append(ind.queens[0:i], other.queens[i:n]...)
    newQ2 := append(other.queens[0:i], ind.queens[i:n]...)

    return NewIndividual(newQ1, newGen), NewIndividual(newQ2, newGen)
}

func tournamentSelect(p Population, k int) *Individual {
    n := len(p)

    var best *Individual = nil
    for i := 0; i < k; i++ {
        j := rand.Intn(n)
        ind := p[j]

        if best == nil || ind.fitness < best.fitness {
            best = ind
        }
    }

    return best
}

/* Solucion sincrona */

func SolveSync(n int) Individual{
    var p Population

    for i := 0; i < 100; i++ {
        ind := createRandomIndividual(n)
        p = append(p, &ind)
    }

    best := *p[0]

    for best.fitness != 0 {
        p, best = generationSync(p)
    }

    fmt.Println(best)
    return best
}

func generationSync(p Population) (Population, Individual) {
    best := *p[0]
    var c Population

    for len(c) < 100 {
        p1 := tournamentSelect(p, 20)
        p2 := tournamentSelect(p, 20)

        c1, c2 := p1.Crossover(*p2)
        
        if rand.Float32() > 0.9 {
            c1 = c1.Mutate()
        }

        if rand.Float32() > 0.9 {
            c2 = c2.Mutate()
        }

        if c1.fitness < best.fitness {
            best = c1
        }

        if c2.fitness < best.fitness {
            best = c2
        }

        c = append(c, &c1, &c2)
    }

    return c, best
}

/* Solucion concurrente */

func SolveConcurrent(n, popSize int) Individual {
    var p Population

    for i := 0; i < popSize; i++ {
        ind := createRandomIndividual(n)
        p = append(p, &ind)
    }

    best := *p[0]

    for best.fitness != 0 {
        p, best = generationConcurrent(p)
    }

    return best
}

func generationConcurrent(p Population) (Population, Individual) {
    best := *p[0]
    var childPop Population
    c := make(chan Individual, 100)

    ncrosses := len(p) / 2

    for i := 0; i < ncrosses; i++ {
        go randGenChild(p, c)
    }

    for i := 0; i < ncrosses * 2; i++ {
        child := <-c
        childPop = append(childPop, &child)
    }

    return childPop, best
}

func randGenChild(p Population, c chan Individual) {
    p1 := tournamentSelect(p, 20)
    p2 := tournamentSelect(p, 20)

    c1, c2 := p1.Crossover(*p2)
        
    if rand.Float32() > 0.9 {
        c1 = c1.Mutate()
    }

    if rand.Float32() > 0.9 {
        c2 = c2.Mutate()
    }

    c <- c1
    c <- c2
}

func main() {
    rand.Seed(time.Now().UTC().UnixNano())

    ind := SolveConcurrent(12, 1000)

    fmt.Println(ind)
}