This post is a follow-follow-up to this post and its follow-up.In those two posts we managed to speed-up the solution of an Alberi puzzle, and to create a one-tree-per-region puzzle.The complete code hereafter can be used to create multi-tree-per-region puzzles.Using DFS I had little chance to find a valid puzzle, so I had to resort to a more exotic genetic algorithm.The first class is the general genetic algorithm impementation (well the simplest of implementations):Genetic algorithm simplicistic and generic implementation.import randomclass GeneticAlgorithm(object):    Genetic algorithm iteration cycle.    The aim is to find an individual with the lowest fitness value    by evolving a population of such individuals.    Each individual is tested against a target value to evaluate its fitness    For each evolution loop part of the best are kept for the next cycle    (retain parameter for evolve method), part of the individuals are kept    indipendently from their fitness (random_select parameter), then these    individuals are mutated according to a mutation rate (mutate paramter),    the rest of the new population is made up crossing randomly picked    individuals.        def __init__(self, individual, fitness, mutate, crossover):        Initializes the evolution functions from the problem factory.        Required argument:        individual -- function to generate a new individual. The function can            take a fixed number of parameters to initialize the individual.            This parameters are to be passed to the population method. The            return argument should be a mutable (see mutate).        fitness -- function to score an individual. An individual and the            target will be passed to the function. The target is set by the            evolve method. The function must return a numeric type.        mutate -- function to mutate in-place an individual. The function will            take a mutable as argument        crossover -- function to create a new individual using the genetic            code of the two individuals passed as argument. The return argument            should be a mutable.                self.individual = individual        self.fitness = fitness        self.mutate_individual = mutate        self.crossover_individuals = crossover    def population(self, count, *args):        Create a number of individuals (i.e. a population).        Required argument:        count -- number of individuals to be created        *args -- parameters to be passed to the individual generation function                return [self.individual(*args) for _ in range(count)]    def grade(self, pop, target):        Find average fitness for a population.                summed = sum(self.fitness(x, target) for x in pop)        return summed / (len(pop) * 1.0)    def evolve(self, pop, target, retain=0.2, random_select=0.1, mutate=0.2):        Genetic algorithm evolution loop.        Required argument:        pop --- count of the elements of the population        target -- target value to obtain        Optional arguments:        retain -- Number of elements whith the lowest fitness to keep at            each iteration        random_select -- Rate of selection of elements whithout fitness            filtering        mutate -- Rate of mutation of elements                graded = [(self.fitness(x, target), x) for x in pop]        graded = [x[1] for x in sorted(graded)]        retain_length = int(len(graded) * retain)        parents = graded[:retain_length]        # randomly add other individuals to        # promote genetic diversity        for individual in graded[retain_length:]:            if random_select > random.random():                parents.append(individual)        # mutate some individuals        for individual in parents:            if mutate > random.random():                self.mutate_individual(individual)        # crossover parents to create children        parents_length = len(parents)        desired_length = len(pop) - parents_length        children = []        while len(children) < desired_length:            male = random.randint(0, parents_length-1)            female = random.randint(0, parents_length-1)            if male != female:                male = parents[male]                female = parents[female]                child = self.crossover_individuals(male, female)                children.append(child)        parents.extend(children)        return parentsThe class __init__ takes as argument the functions needed to generate an individual, evaluate its fitness against a target, mutate (in place) an individual and crossover two individual to make a third one.The methods exposed are population, which creates the initial individuals to be evolved, grade, used to evaluate the global fitness of a population, and evolve, the core of the algorithm, that grows-up the population.The functions I gave to the GeneticAlgorithm class are created by the following class:Fill the empty cells of an Alberi puzzle using a genetic algorithmfrom AlberiCover import Alberifrom GeneticAlgorithm import GeneticAlgorithmimport randomclass AlberiGeneticFactory(object):    Creates the functions needed for the evolution of the GA        def __init__(self, m, n, per_row=2, per_column=2, per_region=2):        Initializes the factory parameters.        Required argument:        n -- Number of rows        m -- Number of columns        Optional arguments:        per_row -- Number of trees per row. (Default: 2.)        per_column -- Number of trees per column. (Default: 2.)        per_region -- Number of trees per region. (Default: 2.)                self.m = m        self.n = n        self.size = size = m * n        self.per_row = per_row        self.per_column = per_column        self.per_region = per_region        neighbour = []        for idx in range(size):            row, col = divmod(idx, m)            neighbour.append(                [endr * n + col for endr in range(row - 1, row + 2)                    if 0 <= endr < m and endr != row] +                [row * n + endc for endc in range(col - 1, col + 2)                    if 0 <= endc < n and endc != col]            )        self.neighbour = neighbour    def individual_function(self):        Returns the function to create an Alberi puzzle.                REGIONLESS = Alberi.REGIONLESS        ORL = ord(REGIONLESS)        neighbour = self.neighbour        def individual(puzzle):             Take a puzzle and makes a single mutation to it.            The mutation is made on a whitespace, labeling it with the letter            of a neighbouring field.            Required argument:            puzzle -- The puzzle to mutate, in the form of a string of n*m                letters indicating the regions. The whitespace ' ' can be                used as a placeholder for a cell with no region assigned.                        neighbour_field = [                set(puzzle[idx] for idx in lst if puzzle[idx] != REGIONLESS)                for lst in neighbour]            options = filter(lambda item: len(item[1])>0, enumerate(neighbour_field))            random.shuffle(options)            mypuzzle = bytearray(puzzle)            for option, vals in options:                if mypuzzle[option] != ORL:                    continue                mypuzzle[option] = random.sample(vals, 1)[0]                break            return mypuzzle        return individual    def fitness_function(self):        Returns the function to evaluate the fitness an Alberi puzzle.                m = self.m        n = self.n        size = self.size        per_row = self.per_row        per_column = self.per_column        per_region = self.per_region        REGIONLESS = Alberi.REGIONLESS        memo_fitness={}        def fitness(individual, target):             Take a partial puzzle and scores it.            The score is equal to the count of empty cells if the puzzle has            but one solution. The score defaults to size if the puzzle has            more than one solution.            The result is memoized, so it can speed up the scoring in case            of duplicate individuals.            Required argument:            individual -- The puzzle to score, in the form of a string of n*m                letters indicating the regions. The whitespace ' ' can be                used as a placeholder for a cell with no region assigned.            target -- unused. Here for compatibility with the GA                        puzzle = str(individual)            out = memo_fitness.get(puzzle)            if out:                return out            print(puzzle)            try:                asolver = Alberi(puzzle, m, n, per_row, per_column, per_region)                sols = [x for _, x in zip(xrange(2), asolver)]                out = puzzle.count(REGIONLESS) if len(sols) == 1 else size            except ValueError:                out = size            memo_fitness[puzzle] = out            return out        return fitness    def mutate_function(self):        Returns the function to mutate an Alberi puzzle.                m = self.m        n = self.n        size = self.size        per_row = self.per_row        per_column = self.per_column        per_region = self.per_region        neighbour = self.neighbour        ORL = ord(Alberi.REGIONLESS)        def mutate_individual(individual):             Take a puzzle and makes a single mutation to it.            The mutation is made in-place.            If the mutation is made on a whitespace, this labels it with            the letter of a neighbouring field.            If the mutation is made on a labeled cell, this verifies that            the remaining cells still form a singly-connected region.            Required argument:            individual -- The puzzle to mutate, in the form of a string of n*m                letters indicating the regions. The whitespace ' ' can be                used as a placeholder for a cell with no region assigned.                        neighbour_field = [                set(individual[idx] for idx in lst if individual[idx] != ORL)                for lst in neighbour]            options = filter(                lambda item: len(item[1]) > 0,                enumerate(neighbour_field))            random.shuffle(options)            for option, vals in options:                if individual[option] == ORL:                    individual[option] = random.sample(vals, 1)[0]                    break                vals.difference_update([individual[option]])                if len(vals) == 0:                    continue                # Tests if removing the element option from the region with                # its letter leaves a simply connected region. First make                # the region array with all the indexes of the cells with the                # letter at the index option (but without option), then do a                # BFS algorithm to assign a value (weight) to each cell (in                # this case is the minimum Manhattan distance from the first                # cell in the array). If every cell has been labeled with a                # value than the region is simply connected                region = [idx for idx, v in enumerate(individual)                    if v == individual[option] and idx != option]                if len(region)==0:                    continue                home = region.pop()                weights = [size+1] * len(region)                curlist = [home]                curval = 0                while len(curlist) > 0:                    newlist = []                    newval = curval + 1                    for list_idx in curlist:                        for cell in neighbour[list_idx]:                            try:                                idx = region.index(cell)                                if weights[idx] > newval:                                    weights[idx] = newval                                    newlist.append(cell)                            except:                                pass                    curlist = newlist                    curval = newval                if all(w <= size for w in weights):                    individual[option] = random.sample(vals, 1)[0]                else:                    continue                break        return mutate_individual    def crossover_function(self):        Returns the function to crossover two puzzles.                def crossover_individuals(male, female):             Returns a new puzzle made crossing the puzzles given as input.            The result is simply the first half of the male input joined to            the last half of the female input.            Required argument:            male, female -- The puzzles to crossover, in the form of a                string of n*m letters indicating the regions. The whitespace                ' ' can be used as a placeholder for a cell with no region                assigned.                        half = len(male) / 2            child = male[:half] + female[half:]            return child        return crossover_individualsThe individuals are created from a starting puzzle by modifying one of the REGIONLESS cells. The fitness of each individual is the count of REGIONLESS cells, if the puzzle has one solution, else the size of the puzzle. The mutation is made by changing a cell to one of its neighbours' label (a check is made to control that the regions are always completely connected). The crossover simply shuffles the first half of a puzzle with the remaining of the other (this is dangerous because no check is made on the validity of the new puzzle).The main solver class is about the same of the one in the last post. I just added a random parameter to the constructor to easily create random puzzles.Solver for an Alberi puzzle using exact coverfrom collections import Iteratorfrom itertools import productfrom ExactCoverExt import ExactCoverclass Alberi(Iterator):    An iterator that yields the solutions to an Alberi problem.    >>> puzzle = '''    ... aabbbccccccc    ... accccccdddee    ... accfcfdddgee    ... afffffddggee    ... aafffdddggee    ... afffddddgggg    ... hffffdiijjjj    ... hffffiiikkkk    ... hhhfiiiiiklk    ... hhhffiilllll    ... hhhffiilllll    ... hhhfffilllll    ... '''    >>> asolver = Alberi(*Alberi.multiline_to_solver_params(puzzle))    >>> print(asolver.decode_solution(next(asolver)))    >>> quit()    aaBbBccccccc    acccccCdddeE    acCfcfdddGee    AfffffDdggee    aafffdddGgEe    AfffDdddgggg    hffffdiiJjJj    hffFfIiikkkk    hhhfiiiiiKlK    hHhffiiLllll    hhhFfIilllll    hHhfffiLllll        REGIONLESS = ' '    VOID = '.'    def __init__(self, puzzle, m, n, per_row=2, per_column=2, per_region=2, random=False):        Construct an Alberi instance.        Required argument:        puzzle -- The puzzle to solve, in the form of a string of n*m            letters indicating the regions. The whitespace ' ' can be used            as a placeholder for a cell with no region assigned. The            period '.' can be used to force an empty cell in the solution.        n -- Number of rows        m -- Number of columns        Optional arguments:        per_row -- Number of trees per row. (Default: 2.)        per_column -- Number of trees per column. (Default: 2.)        per_region -- Number of trees per region. (Default: 2.)        random -- True to make a random scheme                self.m = m        self.n = n        self.puzzle = puzzle        REGIONLESS = Alberi.REGIONLESS        VOID = Alberi.VOID        regions = set(self.puzzle).difference(REGIONLESS + VOID)        trees = m * per_column        if trees != n * per_row or (                trees != len(regions) * per_region and len(regions) > 0):            raise ValueError(Bad puzzle instance. ' + puzzle + ')        def constraints():            for x, y in product(range(m), range(n)):                cell_at_xy = self.puzzle[self.rc2idx(y, x)]                if cell_at_xy != VOID:                    yield (y, x), [                        ('row', y), ('column', x)                    ] + ([('region', cell_at_xy)]                        if cell_at_xy != REGIONLESS else []                    ) + [                        ('neighbour', p, q)                        for p, q in product(range(x, x+2), range(y, y+2))                        if 0 <= p < m and 0 <= q < n                    ]        def counts():            for x in range(m):                yield ('column', x), per_column            for y in range(n):                yield ('row', y), per_row            for r in regions:                yield ('region', r), per_region        self.solver = ExactCover(dict(constraints()),                                 counts=dict(counts()),                                 satisfy=dict(counts()),                                 random=random)    @staticmethod    def multiline_to_solver_params(puzzle):        Construct the set of parameters to call the Alberi constructor.        Required argument:        puzzle -- The puzzle to solve, in the form of a string of n            words, each word consisting of m letters indicating the            regions.        Returns:        puzzle -- A single line representetion of the input        m -- Number of columns        n -- Number of rows                puzzle = puzzle.split()        m = len(puzzle[0])        n = len(puzzle)        puzzle = ''.join(puzzle)        return (puzzle, m, n)    def rc2idx(self, row, col):        Return the index of the cell at (row, col).        return row * self.m + col    def decode_solution(self, solution):        Decode an Alberi solution and return it as a string.        grid = [            list(self.puzzle[(r*self.m):((r+1)*self.m)])            for r in xrange(self.n)        ]        for y, x in solution:            grid[y][x] = grid[y][x].upper()        return '\n'.join(''.join(row) for row in grid)    def solution_to_string(self, solution):        Build a single line string for an Alberi solution.        CELL_OCCUPIED = '*'        CELL_EMPTY = '|'        out = bytearray(CELL_EMPTY * (self.m * self.n))        for y, x in solution:            out[self.rc2idx(y, x)] = CELL_OCCUPIED        return str(out)    def render_board(self, puzzle=None, solution=None):        Draw a board for the Alberi problem.        Optional arguments:        puzzle -- If defined overrides self.puzzle (without changing it).        solution -- If defined the 'trees' are drawn inside the board.                CELL_OCCUPIED = '*'        CELL_EMPTY = ' '        m = self.m        n = self.n        if puzzle is None:            puzzle = self.puzzle        lines = [            puzzle[(r * m):((r + 1) * m)]            for r in xrange(n)        ]        hdiff = [            [                '|' if p[0] != p[1] else ' '                for p in zip(line[:-1], line[1:])            ] + ['|']            for line in lines        ]        vdiff = [            [                '---' if lines[r][c] != lines[r+1][c] else '   '                for c in xrange(m)            ]            for r in xrange(n-1)        ]        vdiff.append(['---' for c in xrange(m)])        if solution is not None:            grid = [                list(CELL_EMPTY * self.m)                for r in xrange(self.n)            ]            for y, x in solution:                grid[y][x] = CELL_OCCUPIED            lines = [''.join(row) for row in grid]        out = '+' + '---+' * m        for r in xrange(n):            out += '\n|' + ''.join([                ' {0} {1}'.format(q[0], q[1])                for q in zip(lines[r], hdiff[r])            ])            out += '\n+' + ''.join([                '{0}+'.format(q)                for q in vdiff[r]            ])        return out    def __next__(self):        return next(self.solver)    next = __next__             # for compatibility with Python 2The AlberiMaker module is where the pieces are glued toghether.Find an Alberi puzzle using a genetic algorithmfrom AlberiCover import Alberifrom random import samplefrom string import ascii_lettersfrom collections import defaultdictfrom GeneticAlgorithm import GeneticAlgorithmfrom AlberiGenetic import AlberiGeneticFactoryfrom itertools import islice, combinationsdef one_per_region_creator(m, n, per_row, per_column, origsol):    Creates a single solution Alberi scheme growing regions around the    trees positioned in the coordinates at origsol.    Required argument:    n -- Number of rows    m -- Number of columns    per_row -- Number of trees per row.    per_column -- Number of trees per column.    origsol -- Coordinates of the trees.        size = m * n    REGIONLESS = Alberi.REGIONLESS    ORL = ord(REGIONLESS)    OVOID = ord(Alberi.VOID)    # Assigns a letter to each tree in the original solution    puzzle = bytearray(REGIONLESS * size)    asolver = Alberi(str(puzzle), m, n, per_row, per_column, per_region=1)    for coords, letter in zip(origsol, ascii_letters):        y, x = coords        puzzle[asolver.rc2idx(y, x)] = letter    # Just a debug output to verify that the solution did not change    print(str(puzzle))    asolver = Alberi(str(puzzle), m, n, per_row, per_column, per_region=1)    print(asolver.solution_to_string(next(asolver)))    # An array of neighbour's positions, to speed up calculations    neighbour = []    for idx in range(size):        row, col = divmod(idx, m)        neighbour.append(            [endr * n + col for endr in range(row - 1, row + 2)                if 0 <= endr < m and endr != row] +            [row * n + endc for endc in range(col - 1, col + 2)                if 0 <= endc < n and endc != col]        )    def recurse(puzzle):        Backtracking function. Assigns a letter to an empty cell,        neighbouring a cell with a letter assigned, and verify that the        new scheme has only one solution                # Makes a set of neighbours for each empty cell in the puzzle        neighbour_field = [            set(puzzle[idx] for idx in lst            if puzzle[idx] != ORL and puzzle[idx] != OVOID)            for lst in neighbour]        # Sort the list of the neighbours placing first the cells with few        # neighbouring fields and then removes the cells without neighbours        best_list = sorted(enumerate(neighbour_field), key=lambda j: len(j[1]))        best_list = filter(lambda item: len(item[1]) > 0, best_list)        mypuzzle = puzzle[:]        for item in best_list:            best = item[0]            if mypuzzle[best] != ORL:                continue            vals = item[1]            for v in vals:                mypuzzle[best] = v                asolver = Alberi(                    str(mypuzzle), m, n, per_row, per_column, per_region=1                )                sols = list(islice(asolver, None, 2))                if len(sols) == 1:                    print(str(mypuzzle))                    if mypuzzle.count(REGIONLESS) == 0:                        yield mypuzzle                    else:                        for rec_puzzle in recurse(mypuzzle):                            yield rec_puzzle            mypuzzle[best] = REGIONLESS    for scheme in recurse(puzzle):        print(asolver.render_board(puzzle=str(scheme)))        yield schemedef region_factory(m, n, per_row, per_column, per_region, scheme):    Joins two or more regions of a one-tree-per-region scheme, and    returns a scheme with per_region trees per region.    The returned scheme usually have more than one solution.    Required argument:    n -- Number of rows    m -- Number of columns    per_row -- Number of trees per row.    per_column -- Number of trees per column.    per_region -- Number of trees per region.    scheme -- Initial scheme. Must be a one-tree-per-region scheme.        if per_region == 1:        yield scheme        return    region_count = m * per_row / per_region    size = m * n    # A dictionary with the region identifier as key and a set of neighbouring    # regions' identifiers as value    neighbour_region = defaultdict(set)    for idx, v in enumerate(scheme):        row, col = divmod(idx, m)        for endr in range(row - 1, row + 2):            if 0 <= endr < m and endr != row:                p = scheme[endr * n + col]                if p == v or p == ord(Alberi.VOID):                    continue                neighbour_region[v].add(p)        for endc in range(col - 1, col + 2):            if 0 <= endc < n and endc != col:                p = scheme[row * n + endc]                if p == v:                    continue                neighbour_region[v].add(p)    def validate_connectivity(myneighbour):        Tests if the graph described in myneighbour is completely connected.        First make the region array with all the indexes of the cells        uncovered. Then do a BFS algorithm to assign a value (weight) to        each cell (in this case is the minimum Manhattan distance from the        first cell in the array). If every cell has been labeled with a        value than the graph is completely connected                region = myneighbour.keys()        if len(region)==0:            return True        home = region[0]        weights = [size+1] * len(region)        weights[region.index(home)] = 0        curlist = [home]        curval = 0        while len(curlist) > 0:            newlist = []            newval = curval + 1            for key in curlist:                for item in myneighbour[key]:                    try:                        idx = region.index(item)                        if weights[idx] > newval:                            weights[idx] = newval                            newlist.append(item)                    except ValueError:                        pass            curlist = newlist            curval = newval        if any(item>size for item in weights):            return False        return True    def region_select_recurse(neighbour_region, selection, depth):        Depth first search for the groups of regions.        Selects one of the remaining items in the list of neighbours of the        last item selected.                neighbour_idx = [            k for k, q in neighbour_region.iteritems()            if len(q.intersection(selection))>0 and not k in selection]        myneighbour = {            k: q            for k, q in neighbour_region.iteritems()            if k != selection[-1]        }        best_list = sorted(neighbour_idx, key=lambda j: len(myneighbour[j].difference(selection)))        for v in best_list:            if depth == 1:                yield selection + (v,)                return            if len(myneighbour[v]) == 0:                continue            for p in region_select_recurse(myneighbour, selection + (v,), depth - 1):                yield p    def super_region_recurse(neighbour_region, super_regions):        Backtracking function. For each region take some element in the        set of neighbouring regions and mark these items as a super-region                best_list = sorted(            neighbour_region,            key=lambda j: len(neighbour_region[j]))        for v in best_list:            no_group = True            if len(neighbour_region[v]) == 0:                return            for p in region_select_recurse(neighbour_region, (v,), per_region - 1):                no_group = False                myneighbour = {                    k: q.difference(p)                    for k, q in neighbour_region.iteritems() if k != v and k not in p                }                if not validate_connectivity(myneighbour):                    continue                mysuper_regions = super_regions + [p]                if len(mysuper_regions) == region_count:                    yield mysuper_regions                else:                    for out in super_region_recurse(myneighbour, mysuper_regions):                        yield out            if no_group:                return    for super_region in super_region_recurse(neighbour_region, []):        translator = bytearray(256)        for c, l in zip(super_region, ascii_letters):            for v in c:                translator[v] = l        translator[ord(Alberi.VOID)] = Alberi.VOID        scheme2 = scheme.translate(translator)        print(str(scheme2))        yield scheme2def reduce_scheme(m, n, per_row, per_column, per_region, scheme3, origsol):    Blanks as much cell as is possible in a region keeping the trees    in origsol connected by a strip of cells.    The returned scheme usually have more than one solution.    Required argument:    n -- Number of rows    m -- Number of columns    per_row -- Number of trees per row.    per_column -- Number of trees per column.    per_region -- Number of trees per region.    scheme3 -- Initial scheme. Must be a one-tree-per-region scheme.    origsol -- Positions of the trees.        if per_region == 1:        for idx in range(len(scheme3)):            if divmod(idx, m) not in origsol:                scheme3[idx] = Alberi.REGIONLESS        return    size = m * n    for letter in set(scheme3):        region = [divmod(idx, m) for idx, value in enumerate(scheme3) if value == letter]        pivots = set(region).intersection(origsol)        # Uses Dijkstra algorithm to find the best path between the cells.        # home is the first of the trees, weights is a list of the distances        # from home, origin is the previous cell in the best path. curlist        # holds the array of the cells to test in the next iteration.        home = pivots.pop()        weights = [size+1] * len(region)        origin = [None] * len(region)        weights[region.index(home)] = 0        curlist = [home]        curval = 0        while any(weights[region.index(pivot)] > size for pivot in pivots):            newlist = []            newval = curval + 1            for r, c in curlist:                for cell in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:                    try:                        idx = region.index(cell)                        if weights[idx] > newval:                            weights[idx] = newval                            origin[idx] = (r, c)                            newlist.append(cell)                    except ValueError:                        pass            curlist = newlist            curval = newval        path = set()        for pivot in pivots:            path.add(pivot)            while origin[region.index(pivot)]:                pivot = origin[region.index(pivot)]                path.add(pivot)        for idx, l in enumerate(scheme3):            if l == letter:                cell = divmod(idx, m)                if cell in path:                    continue                scheme3[idx] = Alberi.REGIONLESSdef make_it(m, n, per_row, per_column, per_region):    Creates a single solution Alberi scheme.    This function find the solution using the following sub-steps:    * Create a solution vector with the desired trees per row and column.    * Create a single-tree-per-region puzzle around these solutions.    * Group the regions of this puzzle to have super-regions with enough      trees per region.    * Leave only a strip of cells joining the solution cells to ensure having      a single solution puzzle. The remaining cells become REGIONLESS.    * Evolve this scheme decreasing the number of REGIONLESS cells while      mantaining a single solution for the result.    * When the scheme has no more REGIONLESS cells, return it.    Required argument:    n -- Number of rows    m -- Number of columns    per_row -- Number of trees per row.    per_column -- Number of trees per column.    per_region -- Number of trees per region.        size = m * n    alberiGeneticFactory = AlberiGeneticFactory(        m, n,        per_row, per_column, per_region)    alberiGenetic = GeneticAlgorithm(        alberiGeneticFactory.individual_function(),        alberiGeneticFactory.fitness_function(),        alberiGeneticFactory.mutate_function(),        alberiGeneticFactory.crossover_function())    target = 0    p_count = 40    asolver = Alberi('a' * size, m, n, per_row, per_column, m * per_row, True)    origsol = next(asolver)    one_per_region = one_per_region_creator(m, n, per_row, per_column, origsol)    for scheme in one_per_region:        for scheme3 in region_factory(m, n, per_row, per_column, per_region, scheme):            str_scheme = str(scheme3)            print(asolver.render_board(puzzle=str_scheme, solution=origsol))            reduce_scheme(m, n, per_row, per_column, per_region, scheme3, origsol)            print(str(scheme3))            lst = [idx for idx, cell in enumerate(scheme3) if cell != ord(Alberi.REGIONLESS)]            print(asolver.render_board(puzzle=str_scheme, solution=[divmod(idx, m) for idx in lst]))            p = alberiGenetic.population(p_count, str(scheme3))            fitness_history = [alberiGenetic.grade(p, target),]            while alberiGenetic.fitness(p[0], target) > 0:                p = alberiGenetic.evolve(p, target)                population_grade = alberiGenetic.grade(p, target)                fitness_history.append(population_grade)                print('{0} {1} {2}'.format(str(p[0]), p[0].count(' '), population_grade))                if population_grade == size:                    break            else:                return str(p[0])if __name__ == '__main__':    m = n = 9    per_row = 2    per_column = 2    per_region = 2    asolver = Alberi('a' * (m * n), m, n, per_row, per_column, m * per_row)    puzzle = make_it(m, n, per_row, per_column, per_region)    print(asolver.render_board(puzzle=puzzle))In this module two iterators are defined: one_per_region and region_factory. The first one takes the solutions of a regionless puzzle and grow regions around those cells, keeping a single solution for the puzzle.The second one takes the regions from the former and take groups of regions to make super-regions that will accomodate more than a tree.This step is needed only to group solutions, in fact, in the reduce_scheme function, we keep only a strip of cells connecting the solutions of the original scheme.Now we (should) have a single-solution-multi-tree-per-region puzzle, with many holes inside.Here it cames the genetic algorithm: we feed this puzzle as the seed for the individuals and let the population evolve.Everything I described is implemented in the make_it function, that takes only the carachteristics of the puzzle and (hopefully) outputs a complete puzzle. Everything is fine you say? Well, the time for a 12 by 12 scheme like the one in the first post is about 24 hours. The number of puzzles tested to find it is not so large: in one of the tests I measured 6935 tentatives (after memoization of the fitness), so the bottleneck is still the puzzle solver. Maybe a change can be made to the ExactCover to solve more than one puzzle at the same time, maybe accepting a topology change after a solution is found... but this would be a really hard task. Other problems aresometimes, the creation of the starting solution vector is too long (maybe the random parameter is not so good for ExactCover);sometimes the region_factory recursion seem to get into a neverending loop (we need some euristic for the task).Any suggestions are very welcome... squeeze your brains and let me know!!PS. I must credit Will Larson for his genetic algorithm implementation. Sorry for the delay but I lost the source link.
Alberi creator. Keepalive
python;performance;game;genetic algorithm