n-Queen puzzle implimentation using Genetic algorithm

main.py

'''
solving n-Queen puzzle using genetic algorithms
source : https://arxiv.org/ftp/arxiv/papers/1802/1802.02006.pdf
author: fatemeh karimi
'''

import numpy
from random import Random, random

def fitness_function(population):
    fitness = numpy.zeros(population.shape[0])
    max_fitness_value = population.shape[1] * (population.shape[1] - 1) / 2

    for i in range(population.shape[0]):
        collisions = 0
        for j, val1 in enumerate(population[i]):
            for k, val2 in enumerate(population[i]):
                if j != k:
                    if val1 == val2:
                        collisions += 1
                    elif abs(val1 - val2) == abs(j - k):
                        collisions += 1

        fitness[i] = max_fitness_value - collisions / 2

    return fitness

#selecting choromosomes with maximum fitness value
def mating_pool(new_population, fitness, n_parents):
    new_parents = numpy.empty((n_parents, new_population.shape[1]))

    for i in range(n_parents):
        max_fitness_i = numpy.where(fitness == numpy.max(fitness))
        max_fitness_i = max_fitness_i[0][0]
        new_parents[i, :] = (new_population[max_fitness_i, :])
        fitness[max_fitness_i] = -999999999
    return new_parents

def cross_over(parents, offspring_size):
    offSpring = numpy.empty(offspring_size)

    for i in range(offspring_size[0]):
        index_parent1 = i % parents.shape[0]
        index_parent2 = (i + 1) % parents.shape[0]
        offSpring[i] = cross_over_parents(parents[index_parent1], parents[index_parent2])

        if i + 1 < offspring_size[0]:
            offSpring[i + 1] = cross_over_parents(parents[index_parent1], parents[index_parent2])
            i += 1
    return offSpring

def cross_over_parents(parent1, parent2):
    tmp_parent1 = numpy.copy(parent1)
    tmp_parent2 = numpy.copy(parent2)
    offSpring = numpy.zeros(parent1.shape)
    allele = int(parent1.shape[0] / 2)
    allele_index = numpy.random.uniform(0, parent1.shape[0] - 1, 1)
    allele_index = int(numpy.round(allele_index))

    for i in range(allele):
        ii = (allele_index + i) % parent1.shape[0]
        offSpring[ii] = tmp_parent1[ii]
        #removing values repeated in both the first and second parent
        for j in range(parent2.shape[0]):
            if tmp_parent2[j] == tmp_parent1[ii]:
                tmp_parent2[j] = 0
                break

    index = 0
    for value in tmp_parent2:
        if value != 0:
            while index < parent1.shape[0] and offSpring[index] != 0:
                index += 1
            if index >= parent1.shape[0]:
                break
            offSpring[index] = value
            index += 1

    return offSpring

def mutation(offSpring):
    mutation_rate = 0.8
    for i in range(offSpring.shape[0]):
        random_value = numpy.random.uniform(0, 1, 1)
        if(random_value <= mutation_rate):
            index1 = numpy.random.uniform(0, offSpring.shape[1] - 1, 1)
            index1 = int(numpy.round(index1))
            index2 = numpy.random.uniform(0, offSpring.shape[1] - 1, 1)
            index2 = int(numpy.round(index2))
            offSpring[i][index1], offSpring[i][index2] = offSpring[i][index2], offSpring[i][index1]
    return offSpring

def show_chess_board(best_ans):
    n = best_ans.shape[0]
    border = '_' * (2 * n + 1)
    for i in range(n):
        str = []
        for j in range(n):
            str.append('.')
        str[int(best_ans[i] - 1)] = 'Q'
        #printing board
        print(border)
        for x in str:
            print('|', end='')
            print(x, end='')
        print('|', end='')
        print("")
    print(border)
    return

def __main__():
    board_size = int(input())

    if board_size < 4:
        print("no solution for board size smaller than 4")
        exit()

    n_genes = board_size
    n_chormosome = 100 #proportional to input size
    n_parents = int(n_chormosome / 4)
    max_fitness_value = board_size * (board_size - 1) / 2
    generation = 0

    population_size = (n_chormosome, n_genes)
    population = numpy.random.uniform(low=1, high=board_size, size=population_size)
    population = numpy.round(population, decimals=0)

    while True:
        generation += 1
        fitness = fitness_function(population)
        if max_fitness_value in fitness:
            print("found result on generation " + str(generation) + ":")
            best_match_index = numpy.where(fitness == max_fitness_value)
            print(population[best_match_index][0])
            show_chess_board(population[best_match_index][0])
            break

        parents = mating_pool(population, fitness, n_parents)
        offSpring = cross_over(parents, (n_chormosome - n_parents, n_genes))
        offspring_mutation = mutation(offSpring)

        population[0:parents.shape[0], :] = parents
        population[parents.shape[0]: , :] = offspring_mutation
        print("Generation = " + str(generation))

    exit()

if __name__ == '__main__':
    __main__()